BOJ 20157 - 화살을 쏘자!

BOJ - 화살을 쏘자!

$gcd(x,\,y)$ 를 $(x,\,y)$ 라고 했을 때, 모든 $x,\,y$ 쌍들을 $\dfrac{x}{(x,\,y)},\dfrac{y}{(x,\,y)}$ 로 바꿔준다음 그 개수를 세주면 된다.

이 때, $x=0~or~y=0$ 인 경우만 적적히 처리해주도록 한다.

void solve() {
   int n;
   cin >> n;
   vector<pair<int, int>> p(n);
   for (auto&[x, y]: p) {
      cin >> x >> y;
      if (x && y) {
         int g = gcd(x, y);
         x /= g;
         y /= g;
      }
   }
   int ans = 0;
   int up = 0, down = 0, left = 0, right = 0;
   vector<pi> g;
   for (int i = 0; i < n; i++) {
      int x = p[i].fi, y = p[i].se;
      if (x == 0) {
         if (y > 0) up++;
         else down++;
         continue;
      } else if (y == 0) {
         if (x > 0) right++;
         else left++;
         continue;
      }
      g.pb(p[i]);
   }
   ans = max({up, down, left, right});

   sort(all(g));
   int mx_group = 0;
   for (int i = 0; i < sz(g); i++) mx_group = max(mx_group, ubi(g, g[i]) - lbi(g, g[i]));
   ans = max(ans, mx_group);

   cout << ans;
}