BOJ 1945 - 직사각형

BOJ 1945 - 직사각형

흔한 문제이다. 각 직사각형의 왼쪽 위와 오른쪽 아래 점을 각도에 따라 정렬해두고 스위핑해주자.

struct event {
   int x, y, z;
};

void solve() {
   int n;
   cin >> n;
   vector<event> e;
   for (int i = 0; i < n; i++) {
      int x1, y1, x2, y2;
      cin >> x1 >> y1 >> x2 >> y2;
      assert(x1 < x2 && y1 < y2);
      e.pb({x1, y2, 1});
      e.pb({x2, y1, -1});
   }
   int overlap = 0;
   sort(all(e), [&](auto &a, auto &b) {
      // ay / ax < by / bx
      if (a.y * b.x == a.x * b.y) {
         // 추가되는 것부터 앞에
         return a.z > b.z;
      }
      return a.y * b.x > a.x * b.y;
   });
   int ans = 0;
   for (int i = 0; i < n * 2; i++) {
      debug(e[i].x, e[i].y, e[i].z);
      overlap += e[i].z;
      ans = max(ans, overlap);
   }
   cout << ans;
}