2001년 가을학기 문제해결기법 - 문제 8

다각형의 면적

평면상에 볼록 다각형 [eqn: P]가 주어져 있다. 다각형 내에 있는 임의의 두 점을 잇는 선분이 다각형 내에 완전히 속하는 다각형을 볼록 다각형이라고 한다. 그리고 변이 모두 x축이나 y축에 평행인 직사각형 [eqn: Q]가 있다. 문제는 [eqn: P]와 [eqn: Q]를 합한 다각형의 면적을 구하는 프로그램을 작성하는 것이다.

예를 들면 아래 그림과 같이 [eqn: P]와 [eqn: Q]가 주어질 수 있다. 그림에서 [eqn: P]는 6각형이며 [eqn: Q]는 점선으로 표시되어 있다. 두 볼록 다각형을 합한 다각형이 항상 볼록 다각형이 되는 것이 아님에 유의한다.

다각형을 나타낼 때는 임의의 한 꼭지점에서 시작하여 다각형을 반시계 방향으로 따라갈 때 만나는 꼭지점의 열(sequence)로 나타낼 수 있다. 꼭지점은 x,y-좌표값으로 나타낸다. 그리고 4각형 [eqn: Q]를 나타내기 위해서는 왼쪽 아래 꼭지점과 오른쪽 위 꼭지점의 좌표만 있으면 충분하다.

프로그램명은 area.cpp(area.c)라고 하고 실행 파일명은 area.exe로 한다. 프로그램의 실행 시간은 10초를 초과할 수 없다.

입력 형식

입력 파일의 이름은 INPUT.TXT이다. 첫째 줄에 볼록 다각형 [eqn: P]의 꼭지점의 수 [eqn: n]이 주어진다. 단,  [eqn: 3 le n le 1000]이다. 둘째 줄부터 [eqn: n+1]번째 줄까지 한 줄에 하나씩 반시계 방향으로 주어지는 꼭지점의 열이 있다. 꼭지점은 x,y-좌표로 나타낸다. 마지막 줄에는 다음과 같이 4각형 [eqn: Q]의 왼쪽 아래 꼭지점의 좌표와 오른쪽 위 꼭지점의 좌표가 주어진다: [eqn: x_L \ y_L \ x_R \ y_R]. 여기서 [eqn: x_L], [eqn: y_L]은 왼쪽 아래 꼭지점, [eqn: x_R], [eqn: y_R]은 오른쪽 위 꼭지점의 좌표이다. 입력되는 숫자 사이에는 공백이 있다.

출력 형식

출력 파일의 이름은 OUTPUT.TXT이다. 첫째 줄에 두 다각형을 합한 다각형의 면적을 출력한다. 두 다각형의 면적의 합이 아닐 수 있음에 주의한다.

입력과 출력의 예

INPUT.TXT

6

4.0  5.0

7.0 3.0

10.0 5.0

10.0 9.0

7.0 11.0

4.0 9.0

6.0 6.0 12.0 9.0

OUTPUT.TXT

42.0