[AC] 2672 여러 직사각형의 전체 면적 구하기

출처 : https://www.acmicpc.net/problem/2672

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.01/2672.cpp

음..이문제는 정말 어렵게 풀었다. 사실 풀지 못하였고 다른사람의 코드를 보고 다시작성하였다. 그게 약 9개월 전이고 이번에 복습겸 다시 풀었다.

먼저 문제는 여러 직사각형의 전체 면적을 구하라고 하는데 입력이 소수이다. 배열에 다 때려박고 계산하는식의 계산을 할 수 없다. 이런걸  brute force라고 하는데 이건 알고리즘이 아니다. 

이 문제의 경우 이런식으로 생각하면 이해가 쉽다. 

이런식으로 도형이 나열되어 있다고 생각해보자. 전체 넓이이니 도형들을 세분화시켜서 그 합을 구해도 값은 같을 것이다.

즉 이런식으로 나누게 된다. 

필자는 귀찮아서 선을 전부 그리지 않았다. 더그려야한다. 대략적인 느낌만 알면 된다. 암튼 모든 점에 대하여 선을 나누면 무수히 많은 사각형이 나온다. 이 사각형들 중에 입력으로 들어온 사각형과 비교하여 포함이 된다면 그 값을 계속 더해주면 된다.

이 알고리즘의 경우 O(n^3) 이 되므로  n값이 크다면 역시 올바른 알고리즘이 되지 못한다. 그래서 과거 검색해보니 인덱스트리나 다른 알고리즘을 사용하면 O(lgn) 까지도 줄어든다고 한다. 그런데 너무 복잡하고 어려워서 포기했던 기억이 있다. 

그러나 이 문제를 풀기에는 n^3도 무방하니 이 알고리즘을 사용해도 되겠다. 그리고 범위를 찾는데 다음과 같이

bool chk(double x1, double x2, double y1, double y2, Rect rect)
{
    //return rect.x1x1 && rect.y1y1;
    return rect.x1<=x1 && rect.x2>=x2 && rect.y1<=y1 && rect.y2>=y2;
}
// 두가지 방법이 있다.

위 에 두가지 방법이 있는데 둘중 아무거나 써도 된다. 대부분의 코드를 보니 상단의 방법을 많이쓰고 과거 트리문제를 풀었을때도 저런 비교를 많이 한다. 하단의 방법도 맞으나, 가급적이면 상단의 방법을 쓰면서 이해하는게 응용하기 훨씬 쉬울거 같다.