1222 - 땅 따먹기 고연전

• Submit
• Status
• Discuss
• Summary

Description

과거 고연전 5전 5패의 뼈아픈 고통도 잊은 채, 연대생들은 오늘도 부질없이 고대에게 덤비고있다. 그래서 오늘의 경기 종목은? 두구두구두구.....바로 땅따먹기다!

땅따먹기는, 돌을 세 번 던져서 원래 자기 땅으로 돌이 돌아오게 되면 돌이 지나갔던 자리를 모두 자신의 땅으로 지정하는, 뭐 대충 그런 게임이다. 고연전 대표로 참가한 땅따먹기 선수들은 다들 한 실력 하는 자들이라서, 땅따먹기 게임 결과 서로의 영역의 모습이 완벽하게 볼록다각형의 모양을 띄었다고한다.

두 선수가 만든 다각형의 땅이 서로 겹치는 부분이 없다면 참 좋겠는데... 경기도중 가끔 땅이 겹치는 상황이 발생하기도 한다. 이 경우 땅이 겹치는 부분은 무효처리가 되서 아무런 효과를 가지지 않는다. 

 

경기 당사자가 아니고 구경꾼인 우리 입장에서는 누가 승리했는지 관심없고, 경기가 얼마나 의미있었는지가 궁금하다. 경기 결과 서로 두 팀이 먹은 땅의 모양이 주어졌을 때, 땅으로 인정되는 부분의 넓이의 합을 구해서, 이 경기가 얼마나 의미있었는지 파악해보자.

Input

입력은 여러개의 테스트케이스로 들어올 수 있다.

각 테스트케이스마 2개의 줄에 걸쳐 다각형의 정보가 주어진다.

첫번째 줄의 첫번째 숫자는 다각형의 점의 개수를 나타내는 수 n이 있고, 이후 2n개의 수는 각 점의 x,y좌표를 의미한다. 점은 시계방향으로 주어지며, 다각형은 항상 볼록다각형임이 보장되어있다.

0으로 시작되는 줄이 있을 경우 입력을 종료한다.

 

입력으로 들어오는 모든 수는 100보다 작은 음이아닌 정수이다.

Output

각 테스트케이스마다 소수점을 포함해 8개의 문자를 출력한다. 두 다각형의 xor한 부분의 넓이를 반올림하여 소수점 아래 2자리까지 출력하며, 불필요한 0은 공백으로 대신 출력한다. 출력은 모두 하나의 줄에서 출력하면 된다. 

출력 형식이 왜 이렇게 복잡한지는 나도 잘 모르겠다...

Sample Input

3  5 5  8 1  2 3
3  5 5  8 1  2 3
4  1 2  1 4  5 4  5 2
6  6 3  8 2  8 1  4 1  4 2  5 3
0

Sample Output

    0.00   13.50