시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 34 13 12 66.667%

문제

상근이는 방에 감시 카메라를 놓으려고 한다.

방은 2차원 평면 위에 있는 볼록 다각형으로 나타낼 수 있다. 카메라는 벽에 놓을 수 있으며, 변의 중간에만 놓을 수 있다.

카메라가 촬영할 수 있는 영역의 영역은 벽과 45도로 교차하는 직선이다. 카메라가 촬영할 수 있는 영역을 구하는 프로그램을 작성하시오.

위의 그림은 문제의 첫 번째 예제를 그림으로 나타낸 것이다. 카메라는 점으로 나타나 있고, 촬영할 수 있는 영역은 회색으로 칠해져 있다. 카메라가 촬영할 수 있는 영역은 방 전체 면적의 71.25% 이다.

입력

첫째 줄에 테스트 케이스의 수가 주어진다. 테스트 케이스의 개수는 100개를 넘지 않는다. 각 테스트 케이스의 첫째 줄에는 방의 꼭짓점의 개수 n (3 ≤ n ≤ 1000)이 주어진다. 다음 n개 줄에는 꼭짓점 좌표 x와 y가 주어진다. (-10,000 ≤ x, y ≤ 10,000)

꼭짓점은 반시계 방향 순서로 주어지며, 모든 각도는 0보다 크고, 180도보다 작다. 카메라는 처음 두 꼭짓점의 중간에 놓여져 있다.

출력

각 테스트 케이스마다 카메라가 촬영할 수 있는 영역의 크기를 출력한다. 방 전체의 크기를 1이라고 했을 때, 상대적인 크기를 출력하면 된다. 절대/상대 오차는 10-6까지 허용된다.

예제 입력 1

2
5
-3 0
3 0
4 5
-2 8
-5 3
4
0 2
2 0
3 1
1 3

예제 출력 1

0.7125
0.5
W3sicHJvYmxlbV9pZCI6IjkzNzQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjMTBcdWMyZGMgXHVjZTc0XHViYTU0XHViNzdjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHViYzI5XHVjNWQwIFx1YWMxMFx1YzJkYyBcdWNlNzRcdWJhNTRcdWI3N2NcdWI5N2MgXHViMTkzXHVjNzNjXHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYzI5XHVjNzQwIDJcdWNjMjhcdWM2ZDAgXHVkM2M5XHViYTc0IFx1YzcwNFx1YzVkMCBcdWM3ODhcdWIyOTQgXHViY2ZjXHViODVkIFx1YjJlNFx1YWMwMVx1ZDYxNVx1YzczY1x1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYmMgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjZTc0XHViYTU0XHViNzdjXHViMjk0IFx1YmNiZFx1YzVkMCBcdWIxOTNcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YzczY1x1YmE3MCwgXHViY2MwXHVjNzU4IFx1YzkxMVx1YWMwNFx1YzVkMFx1YjljYyBcdWIxOTNcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjZTc0XHViYTU0XHViNzdjXHVhYzAwIFx1Y2QyY1x1YzYwMVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzYwMVx1YzVlZFx1Yzc1OCBcdWM2MDFcdWM1ZWRcdWM3NDAgXHViY2JkXHVhY2ZjIDQ1XHViM2M0XHViODVjIFx1YWQ1MFx1Y2MyOFx1ZDU1OFx1YjI5NCBcdWM5YzFcdWMxMjBcdWM3NzRcdWIyZTQuIFx1Y2U3NFx1YmE1NFx1Yjc3Y1x1YWMwMCBcdWNkMmNcdWM2MDFcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWM2MDFcdWM1ZWRcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvaHBvbHlnb24ucG5nXCIgc3R5bGU9XCJoZWlnaHQ6Mzg4cHg7IG9wYWNpdHk6MC45OyB3aWR0aDo0NTRweFwiIFwvPjxcL3A+XHJcblxyXG48cD5cdWM3MDRcdWM3NTggXHVhZGY4XHViOWJjXHVjNzQwIFx1YmIzOFx1YzgxY1x1Yzc1OCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzYwOFx1YzgxY1x1Yjk3YyBcdWFkZjhcdWI5YmNcdWM3M2NcdWI4NWMgXHViMDk4XHVkMGMwXHViMGI4IFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHVjZTc0XHViYTU0XHViNzdjXHViMjk0IFx1YzgxMFx1YzczY1x1Yjg1YyBcdWIwOThcdWQwYzBcdWIwOTggXHVjNzg4XHVhY2UwLCBcdWNkMmNcdWM2MDFcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWM2MDFcdWM1ZWRcdWM3NDAgXHVkNjhjXHVjMGM5XHVjNzNjXHViODVjIFx1Y2U2MFx1ZDU3NFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1Y2U3NFx1YmE1NFx1Yjc3Y1x1YWMwMCBcdWNkMmNcdWM2MDFcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWM2MDFcdWM1ZWRcdWM3NDAgXHViYzI5IFx1YzgwNFx1Y2NiNCBcdWJhNzRcdWM4MDFcdWM3NTggNzEuMjUlIFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWMyMThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOFx1YjI5NCAxMDBcdWFjMWNcdWI5N2MgXHViMTE4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWJjMjlcdWM3NTggXHVhZjJkXHVjOWQzXHVjODEwXHVjNzU4IFx1YWMxY1x1YzIxOCBuICgzICZsZTsgbiAmbGU7IDEwMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU0XHVjNzRjIG5cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YWYyZFx1YzlkM1x1YzgxMCBcdWM4OGNcdWQ0NWMgeFx1YzY0MCB5XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKC0xMCwwMDAgJmxlOyB4LCB5ICZsZTsgMTAsMDAwKTxcL3A+XHJcblxyXG48cD5cdWFmMmRcdWM5ZDNcdWM4MTBcdWM3NDAgXHViYzE4XHVjMmRjXHVhY2M0IFx1YmMyOVx1ZDVhNSBcdWMyMWNcdWMxMWNcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWMwXHViYTcwLCBcdWJhYThcdWI0ZTAgXHVhYzAxXHViM2M0XHViMjk0IDBcdWJjZjRcdWIyZTQgXHVkMDZjXHVhY2UwLCAxODBcdWIzYzRcdWJjZjRcdWIyZTQgXHVjNzkxXHViMmU0LiBcdWNlNzRcdWJhNTRcdWI3N2NcdWIyOTQgXHVjYzk4XHVjNzRjIFx1YjQ1MCBcdWFmMmRcdWM5ZDNcdWM4MTBcdWM3NTggXHVjOTExXHVhYzA0XHVjNWQwIFx1YjE5M1x1YzVlY1x1YzgzOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQgXHVjZTc0XHViYTU0XHViNzdjXHVhYzAwIFx1Y2QyY1x1YzYwMVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzYwMVx1YzVlZFx1Yzc1OCBcdWQwNmNcdWFlMzBcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWJjMjkgXHVjODA0XHVjY2I0XHVjNzU4IFx1ZDA2Y1x1YWUzMFx1Yjk3YyAxXHVjNzc0XHViNzdjXHVhY2UwIFx1ZDU4OFx1Yzc0NCBcdWI1NGMsIFx1YzBjMVx1YjMwMFx1YzgwMVx1Yzc3OCBcdWQwNmNcdWFlMzBcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHViYTc0IFx1YjQxY1x1YjJlNC4gXHVjODA4XHViMzAwXC9cdWMwYzFcdWIzMDAgXHVjNjI0XHVjYzI4XHViMjk0IDEwPHN1cD4tNjxcL3N1cD5cdWFlNGNcdWM5YzAgXHVkNWM4XHVjNmE5XHViNDFjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjkzNzQiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJIaWRkZW4gQ2FtZXJhIiwiZGVzY3JpcHRpb24iOiI8cD5Kb2huIHdhbnRzIHRvIHB1dCBhIGhpZGRlbiBjYW1lcmEgaW4gYSByb29tLiBGb3IgdGhpcyBwcm9ibGVtLCB3ZSBpZ25vcmUgdGhlIHZlcnRpY2FsIGRpbWVuc2lvbiBhbmQgdHJlYXQgdGhlIHJvb20gYXMgYSB0d28tZGltZW5zaW9uYWwgb2JqZWN0LiBUaGUgcm9vbSBoYXMgdGhlIHNoYXBlIG9mIGEgY29udmV4IHBvbHlnb24uIFRoZSBjYW1lcmEgaXMgcGxhY2VkIG9uIGEgd2FsbCwgaGFsZndheSBiZXR3ZWVuIHR3byBjb3JuZXJzLiBUaGUgY2FtZXJhIGhhcyBhIGxpbWl0ZWQgdmlldzogdGhlIGJvcmRlcnMgb2YgdGhlIHZpZXcgYXJlIGdpdmVuIGJ5IHRoZSB0d28gbGluZXMgdGhhdCBpbnRlcnNlY3QgdGhlIHdhbGwgYXQgYSA0NSBkZWdyZWUgYW5nbGUuIEpvaG4gd2FudHMgdG8ga25vdyBob3cgbXVjaCBvZiB0aGUgcm9vbSBpcyB2aXNpYmxlIHRvIHRoZSBjYW1lcmEuIENhbiB5b3UgaGVscCBoaW0/PFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvaHBvbHlnb24ucG5nXCIgc3R5bGU9XCJoZWlnaHQ6Mzg4cHg7IHdpZHRoOjQ1NHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlRoZSByb29tIGFzIGRlc2NyaWJlZCBpbiB0aGUgXHVmYjAxcnN0IHNhbXBsZS4gVGhlIGNhbWVyYSAodGhlIGRvdCkgY2FuIHZpZXcgdGhlIHNoYWRlZCByZWdpb24uIFRoZSBsaW1pdHMgYXJlIGdpdmVuIGJ5IGxpbmVzIHRoYXQgbWFrZSBhIDQ1IGRlZ3JlZSBhbmdsZSB3aXRoIHRoZSBiYXNlIHdhbGwuIFRoZSBhcmVhIG9mIHRoZSBzaGFkZWQgcmVnaW9uIGlzIDcxLjI1JSBvZiB0aGUgdG90YWwgYXJlYSBvZiB0aGUgcm9vbS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPk9uIHRoZSBcdWZiMDFyc3QgbGluZSBvbmUgcG9zaXRpdmUgbnVtYmVyOiB0aGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMsIGF0IG1vc3QgMTAwLiBBZnRlciB0aGF0IHBlciB0ZXN0IGNhc2U6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+b25lIGxpbmUgd2l0aCBhIHNpbmdsZSBpbnRlZ2VyIG4gKDMgJmxlOyBuICZsZTsgMSAwMDApOiB0aGUgbnVtYmVyIG9mIGNvcm5lcnMgb2YgdGhlIHJvb20uPFwvbGk+XHJcblx0PGxpPm4gbGluZXMgd2l0aCB0d28gc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzIHggYW5kIHkgKC0xMCAwMDAgJmxlOyB4LCB5ICZsZTsgMTAgMDAwKTogdGhlIGNvb3JkaW5hdGVzIG9mIHRoZSBjb3JuZXJzLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlRoZSBjb3JuZXJzIGFyZSBnaXZlbiBpbiBjb3VudGVyY2xvY2t3aXNlIG9yZGVyLiBBbGwgYW5nbGVzIGFyZSBzdHJpY3RseSBiZXR3ZWVuIDAgYW5kIDE4MCBkZWdyZWVzLiBUaGUgY2FtZXJhIGlzIHBsYWNlZCBleGFjdGx5IGhhbGZ3YXkgYmV0d2VlbiB0aGUgXHVmYjAxcnN0IHR3byBjb3JuZXJzIGluIHRoZSBpbnB1dC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5QZXIgdGVzdCBjYXNlOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPm9uZSBsaW5lIHdpdGggb25lIFx1ZmIwMm9hdGluZyBwb2ludCBudW1iZXI6IHRoZSByYXRpbyBvZiB0aGUgYXJlYSB0aGF0IHRoZSBjYW1lcmEgY2FuIHNlZSBhbmQgdGhlIHRvdGFsIGFyZWEgb2YgdGhlIHJvb20uIFRoaXMgbnVtYmVyIHNob3VsZCBiZSBhY2N1cmF0ZSB1cCB0byAxMDxzdXA+LTY8XC9zdXA+IHJlbGF0aXZlIG9yIGFic29sdXRlIHByZWNpc2lvbi48XC9saT5cclxuPFwvdWw+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==