https://www.acmicpc.net/problem/30447
이 문제를 풀기 전에 1077번 문제를 먼저 풀고 오면 도움이 되니 먼저 풀도록 합시다.
직사각형 모양인 종이의 가로와 세로의 길이, 접는 선을 이루는 종이 위의 두 점이 차례로 주어지면, 그 접는 선을 기준으로 접어서 생기는 새로운 도형의 넓이(의 정수부)를 구하는 문제입니다.
“그거” 를 제외한 별다른 반례는 없으므로 설명에 예제를 참고하여 사용하도록 하겠습니다.
(0, 0)부터 반시계방향으로 A, B, C, D라 하며, 접는 선을 이루는 두 점을 각각 P, Q 라고 합시다. P, Q의 순서는 상관 없습니다.
선분 PQ를 따라 접었을 때 옮겨지는 점 C와 옮겨진 점 C’는 PQ에 대해 선대칭이므로 C’와 C의 중점이 접는 선 위에 존재함을 이용해 C’의 좌표를 쉽게 구할 수 있습니다.
종이를 접었을 때 생기는 새로운 도형은 예제처럼 볼록하지 않을 수 있어 넓이를 제대로 구하기 위해선 새로 구한 다각형의 꼭짓점의 순서가 정확히 맞아야 합니다.
그래서 모든 좌표 자체를 교차 판정 등을 이용해 구하는 것은 쉽겠으나, 그 순서를 각도 정렬이나 case work 등의 방법으로 찾으려고 시도할 수도 있을 것 같긴 합니다… 만 예제와 같은 경우처럼 선분 C’P와 선분 C’Q 때문에 생기는 교차점 처리 등으로 인해 예외가 상당히 많이 생길 수 있어 모든 케이스를 통과하는 코드를 짜긴 어려울 것이라 생각하여 시도하지는 않았습니다. (물론 이렇게 푸신 분도 있을 것 같습니다.) 조금만 단순하게 생각해봅시다.
예시에서 새로 만들어지는 다각형에는 삼각형 PQC'(접힐때 움직인 점과 P, Q의 합집합)와 오각형 ABQPD(접힐때 움직이지 않은 점과 P, Q의 합집합)가 겹쳐지는 영역이 있음을 확인할 수 있습니다. 따라서 어느 경우든 구하는 넓이는 두 다각형의 넓이의 합에서 겹치는 넓이를 한번 빼주면 됩니다.
조금만 생각해보면 PQC’는 PQC와 그냥 합동인 도형이기 때문에 그냥 직사각형의 넓이에서 intersection area 만 빼주면 된다는 것을 알 수 있습니다.
C’가 원래의 직사각형의 경계 혹은 내부에 존재하는 경우는 area(P, Q, C’) 자체가 intersection area가 되기 때문에 다른 예외 처리는 필요하지 않습니다.
위 내용을 구현하면… 축하합니다! 틀렸습니다.
실수 오차가 이렇게 무섭습니다.
처음 AC를 받았을 때는 Decimal 모듈을 사용해서 prec = 100에 소수점 아래 15자리에서 반올림한 결과를 사용했는데,
Decimal 없이 소수점 아래 7자리쯤에서 반올림하고 계산해도 AC를 받는 것을 보면 필요 없었던 것 같네요. 예를 들어 답이 60인데 반올림 전에는 59.9999999..인 데이터가 있는 것으로 보입니다.
진짜로 맞았습니다!
