[백준]여러 직사각형의 전체 면적 구하기(2672)

문제 링크 : [백준]여러 직사각형의 전체 면적 구하기(2672)

2672번: 여러 직사각형의 전체 면적 구하기

 

문제 설명

여러개의 직사각형의 위치가 주어졌을 때, 직사각형들이 차지하는 총 면적을 구하세요.

직사각형의 크기 및 위치는 소수점 한자리까지 주어지며, 면적이 소수점이 없으면 정수로 출력, 소수점이 존재하면 소수점 둘째자리까지 출력하세요.

 

입력

N(직사각형의 갯수, 1 <= N <= 30)

X_i Y_i W_i H_i(X_i : 직사각형 왼쪽 좌표, Y_i : 직사각형의 아랫쪽 좌표, W_i : 직사각형의 너비, H_i : 직사각형의 높이, 0 < X_i, Y_i, W_i, H_i <= 1,000.0)

4
52.7 22.9 27.3 13.3
68.8 57.6 23.2 8.0
20.0 48.0 37.0 23.5
41.5 36.2 27.3 21.4

 

출력

1853.61

 

카테고리

#스와핑

 

시간 복잡도 상한

O(N⁵) 혹은 O(W * H)

 

해결 방법

1. W * H 만큼의 테이블을 만들고, 사각형이 주어지면 각 범위들을 1로 칠해주고, 마지막에 모든 칸을 돌면서 칠해진 칸을 세어보면 됩니다.
2. 하지만 여기서 문제는 좌표값들이 소수점 한자리가 나올 수 있어서 배열로는 표시할 수 없습니다.
3. 그러나 문제에서 소수점 한자리까지만 나온다고 하였으니, 10을 곱해주면 정수로 만들 수 있습니다.
4. 그래도 문제가 있습니다. N번동안 모든 범위를 덮는 사각형이 나온다면, 10,000*10,000*30(10,000인 이유는 3에서 10을 곱했기 때문입니다.)이므로 타임아웃이 납니다.
5. 그런데 여기서 살펴볼 것이 있습니다.
6. 세로 선을 왼쪽부터 관찰하면, 맨 왼쪽선부터 시작하여 다음 왼쪽 선이 나올 때까지는 사각형의 높이가 변하지 않습니다.
7. 백준 사이트 예제를 보시면 맨 왼쪽에 있는 사각형의 왼쪽 세로선에서 다음 사각형 세로 선이 나타날 때까지 사각형의 높이가 변하지 않습니다.
8. 이 성질을 이용하여, 모든 좌표들을 가지고 계산하지 않고, 값의 변화가 일어날 수 있는 위치만 계산을 해줍니다.
9. 각 사각형 하나마다 아래와 같은 정보로 만들어 관리합니다.
   
   1. (사각형이 시작하는 X좌표, 아래쪽 Y좌표, 위쪽 Y좌표, 1(현재 Y축 범위를 커버하는 사각형이 생겼다는 의미))
   2. (사각형이 끝나는 X좌표, 아래쪽 Y좌표, 위쪽 Y좌표, -1(현재 Y축 범위를 커버하는 사각형이 끝났다는 의미))
10. 그리고 X좌표를 기준으로 정렬합니다.
11. 맨 왼쪽 세로선부터 탐색하면서, (현재 세로선의 X좌표 - 이전 세로선의 X좌표) * (두 세로선 사이에서 커버되는 세로 칸 수)를 계산합니다.
12. 두 세로선 사이에서 커버되는 세로 칸 수는 9에서 만든 두 Y좌표를 가지고 만듭니다.
13. 아래쪽 좌표부터 위쪽좌표까지 돌면서 카운팅하기 위해 만들었던 1 혹은 -1을 더해줍니다.
14. 그 후에 각 Y좌표의 값이 1 이상이면 사각형이 존재하는 것이고, 0이면 사각형이 없는 것이므로 전체 세로 범위를 탐색하면서 1이상인 칸의 수를 세면 11에서 사용 할 수 있는 값이 됩니다.
15. 이렇게 모든 범위에 대해 값들을 더하여 출력하면 됩니다.
16. 행복하게 끝날 줄 알았으나, 복병이 있었습니다.
17. double을 int로 바꾸는 과정에서 오차가 발생하였습니다.
18. 오차 보정을 위하여 입력받은 각 값에 0.001을 더하여 실제 값에는 영향을 주지 않고 오차를 보완할 수 있도록 하였습니다.

시간복잡도

O(M)

코드

#include<cstdio>
#include<algorithm>
using namespace std;
struct N{
    int x,f,t,c;
    bool operator<(const N&a)const{
        if(x!=a.x)return x<a.x;
        return c<a.c;
    }
}d[61];
int n,i,j,t[20001],v,s;
double x,y,z,q;
int main(){
    scanf("%d",&n);
    n*=2;
    for(i=1;i<=n;i+=2){
        scanf("%lf%lf%lf%lf",&x,&y,&z,&q);
        x+=0.001;y+=0.001;z+=0.001;q+=0.001;
        d[i].x=x*10;
        d[i+1].x=(x+z)*10;
        d[i].f=d[i+1].f=y*10;
        d[i].t=d[i+1].t=(y+q)*10;
        d[i].c=1;d[i+1].c=-1;
    }
    sort(d+1,d+n+1);
    for(i=1;i<=n;i++){
        for(v=j=0;j<20001;j++)v+=!!t[j];
        s+=(d[i].x-d[i-1].x)*v;
        for(j=d[i].f;j<d[i].t;j++)t[j]+=d[i].c;
    }
    printf("%d",s/100);
    if(s%100)printf(".%02d",s%100);
}