[백준] 1945 직사각형

문제 링크 : www.acmicpc.net/problem/1945

1945번: 직사각형

문제 유형

Sweeping

 

다음과 같은 예제를 보자.

이 예제에서 각 직사각형을 관통하기 시작하는 직선과 관통이 끝나는 직선을 알기 위해서는,

다음 그림처럼 각 직사각형마다 두 개의 점만 알면 된다.

빨간색 점은 직사각형을 관통하기 시작하는 직선과의 교점이며,

파란색 점은 직사각형의 관통이 끝나는 직선과의 교점이다.

따라서 우리는 다음과 같은 순서로 이 점들을 훑으며 정답을 구할 수 있다.

기울기가 높은 점부터 낮은 순으로 훑는다.

각 점마다 원점과의 직선 기울기를 구해, 이 기울기의 내림차순으로 점들을 정렬한다.

시작하는 점(빨간색 점)에는 가중치 1을, 끝나는 점(파란색 점)에는 가중치 -1을 부여한다.

정렬된 점들을 훑으며 각 점들을 만날 때마다 그 점의 가중치를 더해, 가중치 합의 최댓값을 구하면 된다.

 

주의할 점은, 같은 직선상의 두 점이 각각 시작점과 끝점일 때, 시작점을 우선적으로 계산해야 한다는 것이다.

 

[코드]

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
typedef pair<int, int> p;
typedef pair<p, int> sp;
 
int n;
vector<sp> points;
 
bool compare(sp a, sp b) {
    //원점으로부터 직선의 기울기 순으로 내림차순 정렬
    double grad_a = (double)a.first.second / a.first.first;    
    double grad_b = (double)b.first.second / b.first.first;
    if (grad_a == grad_b) return a.second > b.second;
    return grad_a > grad_b;
}
 
int sweeping() {
    int ret = 0, cnt = 0;
    for (int i = 0; i < points.size(); i++) {
        ret = max(ret, cnt);
        cnt += points[i].second;
    }
    return ret;
}
 
void init() {
    int x1, y1, x2, y2;
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        cin >> x1 >> y1 >> x2 >> y2;
        //(x1, y1)은 왼쪽 아래, (x2, y2)는 오른쪽 위
        //필요한 점은 왼쪽 위와 오른쪽 아래이므로 다음과 같이 저장
        points.push_back({ {x1, y2}, 1 });    //직사각형 시작점
        points.push_back({ { x2, y1 }, -1 }); //직사각형 끝점
    }
 
    sort(points.begin(), points.end(), compare);
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(NULL);
 
    init();
    printf("%d\n", sweeping());
 
    return 0;
}