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

Problem Solving

1ssrek 2016. 8. 30. 23:52

풀었던 문제 중 제일 많이 틀렸습니다!! 인 것 같다.

ㅜㅜ...

처음 접근은

1. 사각형의 넓이를 다 더한다.

2. 두 사각형이 겹치는 넓이를 뺀다.

이렇게였는데, 틀렸다.

위와같은 방법으로 접근하려면

1.사각형의 넓이를 다 더한다.

2. 두 사각형이 겹치는 넓이를 뺀다.

3. 세 사각형이 겹치는 넓이를 더한다.

4. 네 사각형이 겹치는 넓이를 뺀다.

5. 다섯 사각형이 겹치는 넓이를 더한다.

....

이와같이 접근해야하므로 시간복잡도를 감당할 수 없을 것 같아 포기.

생각을 거듭하다보면, 이런 생각을 떠올릴 수 있다.

위와같은 사각형이 주어졌을 때,

위와같이 영역을 모두 쪼갠다.

이후 각 영역이 사각형 안에 들어있는가?를 판단하면 된다.

시간복잡도는 N^3.

간단해보이지만 여러 번 틀린이유는 소수 다루는 데서 발생했다.

문제에서"소수점 2자리까지 출력, 소수점 이하 자리수가 없을 경우 출력하지 않는다."를 다루는게 버거웠는데, 단순히 ((long long)answer == answer)? 정수출력:2자리까지출력

이렇게해주면 답은 띄우는 것 같다.

문제는 알수없는 버그??에서 비롯되었다.

"(s[k].x <= lx[i - 1] && lx[i] <= s[k].x + s[k].w && s[k].y <= ly[j - 1] && ly[j] <= s[k].y + s[k].h)" -> 틀림!

"(s[k].x1 <= lx[i - 1] && lx[i] <= s[k].x2 && s[k].y1 <= ly[j - 1] && ly[j] <= s[k].y2)" -> 정답!

해당 영역이 사각형안에 있는가를 판단할 때

사각형의 한쪽점, width,height으로 판단하면 틀렸습니다.

사각형의 left,right,up,down으로 판단하면 정답입니다.

이유는 알 수 없다.

codeup에서는 AC를 띄웠으니 코딩의 문제는 아닌 것 같은데,... 저장공간없이 실수연산하면 값이 달라지는건가?