시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 27 8 7 33.333%

문제

희현이는 환상의 나라 에벌랜드가 새롭게 추진하는 래프팅 프로젝트의 디자이너로 취직을 하였다. 희현이는 바깥의 다각형이 안의 다각형을 포함하게끔 두 개의 다각형 그린 후, 그 사이 빈 공간을 래프팅 트랙으로 디자인 하였다.

자 이제 트랙을 만들었으니 튜브의 크기를 결정할 일만 남았다. 사람들을 '하태핫해'하게끔 만들고 싶은 희현이는 원형 튜브가 트랙을 움직이면서 자유롭게 회전이 되도록 만들고 싶다. 또한 튜브는 가능한 많은 사람이 탈 수 있도록 크게 만들고 싶지만 튜브의 크기가 너무 크면 트랙에 걸리게 되어 버린다.

이 때, 튜브의 크기를 얼마나 크게해야 될까?

입력

첫째 줄에는 테스트 케이스의 수가 주어진다. 최대 100개이다.

각 테스트 케이스마다 첫째 줄에는 내부 다각형의 점의 수 ni (3 ≤ ni ≤ 100)가 주어진다. 그 후 ni개 줄에는 각 점의 (x, y)좌표가 순서대로 주어진다.

그 다음 줄에는 외부 다각형의 점의 수 no (3 ≤ no ≤ 100)가 주어진다. 그 후 no개 줄에는 각 점의 (x, y)좌표가 순서대로 주어진다.

모든 좌표의 절대값은 1000 이하이고, 다각형의 점은 시계 혹은 반시계 방향으로 주어진다. 두 개의 다각형은 서로 겹치거나 만나지 않는다. 항상 외부 다각형은 내부 다각형을 포함한다.

출력

각 테스트케이스마다 튜브의 최대 크기를 출력한다. 상대/절대 오차가 10^-6 미만인 경우 정답으로 처리한다.

예제 입력 1

2
4
-5 -5
5 -5
5 5
-5 5
4
-10 -10
-10 10
10 10
10 -10
3
0 0
1 0
1 1
5
3 -3
3 3
-4 2
-1 -1
-2 -2

예제 출력 1

2.5
0.70710678

힌트

W3sicHJvYmxlbV9pZCI6IjM2ODgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI3OThcdWQ1MDRcdWQzMDUgXHViNTE0XHVjNzkwXHVjNzc4IiwiZGVzY3JpcHRpb24iOiI8cD5cdWQ3NmNcdWQ2MDRcdWM3NzRcdWIyOTQgXHVkNjU4XHVjMGMxXHVjNzU4IFx1YjA5OFx1Yjc3YyBcdWM1ZDBcdWJjOGNcdWI3OWNcdWI0ZGNcdWFjMDAgXHVjMGM4XHViODZkXHVhYzhjIFx1Y2Q5NFx1YzljNFx1ZDU1OFx1YjI5NCBcdWI3OThcdWQ1MDRcdWQzMDUgXHVkNTA0XHViODVjXHVjODFkXHVkMmI4XHVjNzU4Jm5ic3A7XHViNTE0XHVjNzkwXHVjNzc0XHViMTA4XHViODVjJm5ic3A7XHVjZGU4XHVjOWMxXHVjNzQ0IFx1ZDU1OFx1YzYwMFx1YjJlNC4mbmJzcDtcdWQ3NmNcdWQ2MDRcdWM3NzRcdWIyOTQgXHViYzE0XHVhZTY1XHVjNzU4IFx1YjJlNFx1YWMwMVx1ZDYxNVx1Yzc3NCZuYnNwO1x1YzU0OFx1Yzc1OCBcdWIyZTRcdWFjMDFcdWQ2MTVcdWM3NDQgXHVkM2VjXHVkNTY4XHVkNTU4XHVhYzhjXHViMDU0Jm5ic3A7XHViNDUwIFx1YWMxY1x1Yzc1OCBcdWIyZTRcdWFjMDFcdWQ2MTUgXHVhZGY4XHViOWIwIFx1ZDZjNCwmbmJzcDtcdWFkZjggXHVjMGFjXHVjNzc0IFx1YmU0OCBcdWFjZjVcdWFjMDRcdWM3NDQmbmJzcDtcdWI3OThcdWQ1MDRcdWQzMDUmbmJzcDtcdWQyYjhcdWI3OTlcdWM3M2NcdWI4NWMmbmJzcDtcdWI1MTRcdWM3OTBcdWM3NzggXHVkNTU4XHVjNjAwXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3OTAgXHVjNzc0XHVjODFjIFx1ZDJiOFx1Yjc5OVx1Yzc0NCBcdWI5Y2NcdWI0ZTRcdWM1YzhcdWM3M2NcdWIyYzgmbmJzcDtcdWQyOWNcdWJlMGNcdWM3NTggXHVkMDZjXHVhZTMwXHViOTdjIFx1YWNiMFx1YzgxNVx1ZDU2MCBcdWM3N2NcdWI5Y2MgXHViMGE4XHVjNTU4XHViMmU0LiBcdWMwYWNcdWI3OGNcdWI0ZTRcdWM3NDQgJiMzOTtcdWQ1NThcdWQwZGNcdWQ1NmJcdWQ1NzQmIzM5O1x1ZDU1OFx1YWM4Y1x1YjA1NCBcdWI5Y2NcdWI0ZTRcdWFjZTAgXHVjMmY2XHVjNzQwIFx1ZDc2Y1x1ZDYwNFx1Yzc3NFx1YjI5NCBcdWM2ZDBcdWQ2MTUmbmJzcDtcdWQyOWNcdWJlMGNcdWFjMDAmbmJzcDtcdWQyYjhcdWI3OTlcdWM3NDQgXHVjNmMwXHVjOWMxXHVjNzc0XHViYTc0XHVjMTFjIFx1Yzc5MFx1YzcyMFx1Yjg2ZFx1YWM4YyBcdWQ2OGNcdWM4MDRcdWM3NzQgXHViNDE4XHViM2M0XHViODVkIFx1YjljY1x1YjRlNFx1YWNlMCBcdWMyZjZcdWIyZTQuIFx1YjYxMFx1ZDU1YyBcdWQyOWNcdWJlMGNcdWIyOTQgXHVhYzAwXHViMmE1XHVkNTVjIFx1YjljZVx1Yzc0MCBcdWMwYWNcdWI3OGNcdWM3NzQgXHVkMGM4IFx1YzIxOCBcdWM3ODhcdWIzYzRcdWI4NWQgXHVkMDZjXHVhYzhjIFx1YjljY1x1YjRlNFx1YWNlMCZuYnNwO1x1YzJmNlx1YzljMFx1YjljYyZuYnNwO1x1ZDI5Y1x1YmUwY1x1Yzc1OCBcdWQwNmNcdWFlMzBcdWFjMDAgXHViMTA4XHViYjM0IFx1ZDA2Y1x1YmE3NCBcdWQyYjhcdWI3OTlcdWM1ZDAgXHVhYzc4XHViOWFjXHVhYzhjIFx1YjQxOFx1YzViNCBcdWJjODRcdWI5YjBcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NCZuYnNwO1x1YjU0YywgXHVkMjljXHViZTBjXHVjNzU4IFx1ZDA2Y1x1YWUzMFx1Yjk3YyBcdWM1YmNcdWI5YzhcdWIwOTggXHVkMDZjXHVhYzhjXHVkNTc0XHVjNTdjIFx1YjQyMFx1YWU0Yz88XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWMyMThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWNkNWNcdWIzMDAgMTAwXHVhYzFjXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0Jm5ic3A7XHViMGI0XHViZDgwIFx1YjJlNFx1YWMwMVx1ZDYxNVx1Yzc1OCZuYnNwO1x1YzgxMFx1Yzc1OCBcdWMyMTgmbmJzcDtuaSZuYnNwOygzICZsZTsgbmkmbmJzcDsmbGU7IDEwMClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFkZjggXHVkNmM0Jm5ic3A7bmlcdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMSBcdWM4MTBcdWM3NTggKHgsIHkpXHVjODhjXHVkNDVjXHVhYzAwIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWRmOCBcdWIyZTRcdWM3NGMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YzY3OFx1YmQ4MCBcdWIyZTRcdWFjMDFcdWQ2MTVcdWM3NTggXHVjODEwXHVjNzU4IFx1YzIxOCBubyZuYnNwOygzICZsZTsgbm8mbmJzcDsmbGU7IDEwMClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiZuYnNwO1x1YWRmOCBcdWQ2YzQmbmJzcDtub1x1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxIFx1YzgxMFx1Yzc1OCAoeCwgeSlcdWM4OGNcdWQ0NWNcdWFjMDAgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYWE4XHViNGUwIFx1Yzg4Y1x1ZDQ1Y1x1Yzc1OCBcdWM4MDhcdWIzMDBcdWFjMTJcdWM3NDAgMTAwMCBcdWM3NzRcdWQ1NThcdWM3NzRcdWFjZTAsIFx1YjJlNFx1YWMwMVx1ZDYxNVx1Yzc1OCBcdWM4MTBcdWM3NDAgXHVjMmRjXHVhY2M0IFx1ZDYzOVx1Yzc0MCBcdWJjMThcdWMyZGNcdWFjYzQgXHViYzI5XHVkNWE1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViNDUwIFx1YWMxY1x1Yzc1OCBcdWIyZTRcdWFjMDFcdWQ2MTVcdWM3NDAgXHVjMTFjXHViODVjIFx1YWNiOVx1Y2U1OFx1YWM3MFx1YjA5OCBcdWI5Y2NcdWIwOThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LiBcdWQ1NmRcdWMwYzEgXHVjNjc4XHViZDgwIFx1YjJlNFx1YWMwMVx1ZDYxNVx1Yzc0MCBcdWIwYjRcdWJkODAgXHViMmU0XHVhYzAxXHVkNjE1XHVjNzQ0IFx1ZDNlY1x1ZDU2OFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4XHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0IFx1ZDI5Y1x1YmUwY1x1Yzc1OCBcdWNkNWNcdWIzMDAgXHVkMDZjXHVhZTMwXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4mbmJzcDtcdWMwYzFcdWIzMDBcL1x1YzgwOFx1YjMwMCBcdWM2MjRcdWNjMjhcdWFjMDAgMTBeLTYgXHViYmY4XHViOWNjXHVjNzc4IFx1YWNiZFx1YzZiMCBcdWM4MTVcdWIyZjVcdWM3M2NcdWI4NWMgXHVjYzk4XHViOWFjXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjM2ODgiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJXaGl0ZSBXYXRlciBSYWZ0aW5nIiwiZGVzY3JpcHRpb24iOiI8cD5Zb3UgaGF2ZSBiZWVuIGhpcmVkIGJ5IGEgYmlnIHRoZW1lIHBhcmsgdG8gZGVzaWduIGEgbmV3IGF0dHJhY3Rpb246IGEgd2hpdGUgd2F0ZXIgcmFmdGluZyByaWRlLiBZb3UgYWxyZWFkeSBkZXNpZ25lZCB0aGUgdHJhY2s7IGl0IGlzIGEgcm91bmQgdHJpcCB0aGF0IGlzIGRlc2NyaWJlZCBieSBhbiBpbm5lciBhbmQgYW4gb3V0ZXIgcG9seWdvbi4gVGhlIHNwYWNlIGluIGJldHdlZW4gdGhlIHR3byBwb2x5Z29ucyBpcyB0aGUgdHJhY2suPFwvcD5cclxuXHJcbjxwPllvdSBzdGlsbCBuZWVkIHRvIGRlc2lnbiB0aGUgcmFmdHMsIGhvd2V2ZXIuIEl0IGhhcyBiZWVuIGRlY2lkZWQgdGhhdCB0aGV5IHNob3VsZCBiZSBjaXJjdWxhciwgc28gdGhhdCB0aGV5IGNhbiBzcGluIGZyZWVseSBhbG9uZyB0aGUgdHJhY2sgYW5kIGluY3JlYXNlIHRoZSBmdW4gYW5kIGV4Y2l0ZW1lbnQgb2YgdGhlIHJpZGUuIEJlc2lkZXMgdGhhdCwgdGhleSBzaG91bGQgYmUgYXMgYmlnIGFzIHBvc3NpYmxlIHRvIGZpdCB0aGUgbWF4aW11bSBudW1iZXIgb2YgcGVvcGxlLCBidXQgdGhleSBjYW4mcnNxdW87dCBiZSB0b28gYmlnLCBmb3Igb3RoZXJ3aXNlIHRoZXkgd291bGQgZ2V0IHN0dWNrIHNvbWV3aGVyZSBvbiB0aGUgdHJhY2suPFwvcD5cclxuXHJcbjxwPldoYXQgaXMgdGhlIG1heGltdW0gcmFkaXVzIG9mIHRoZSByYWZ0cyBzbyB0aGF0IHRoZXkgY2FuIGNvbXBsZXRlIHRoZSB0cmFjaz88XC9wPlxyXG4iLCJpbnB1dCI6IjxwPk9uIHRoZSBmaXJzdCBsaW5lIG9uZSBwb3NpdGl2ZSBudW1iZXI6IHRoZSBudW1iZXIgb2YgdGVzdGNhc2VzLCBhdCBtb3N0IDEwMC4gQWZ0ZXIgdGhhdCBwZXIgdGVzdGNhc2U6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+T25lIGxpbmUgd2l0aCBhbiBpbnRlZ2VyIG48c3ViPmk8XC9zdWI+ICgzICZsZTsgbjxzdWI+aTxcL3N1Yj4gJmxlOyAxMDApOiB0aGUgbnVtYmVyIG9mIHBvaW50cyBvZiB0aGUgaW5uZXIgcG9seWdvbi48XC9saT5cclxuXHQ8bGk+bjxzdWI+aTxcL3N1Yj4gbGluZXMgd2l0aCB0d28gaW50ZWdlcnMgZWFjaDogdGhlIGNvb3JkaW5hdGVzIG9mIHRoZSBwb2ludHMgb2YgdGhlIGlubmVyIHBvbHlnb24gaW4gY29uc2VjdXRpdmUgb3JkZXIuPFwvbGk+XHJcblx0PGxpPk9uZSBsaW5lIHdpdGggYW4gaW50ZWdlciBuPHN1Yj5vPFwvc3ViPiAoMyAmbGU7IG48c3ViPm88XC9zdWI+ICZsZTsgMTAwKTogdGhlIG51bWJlciBvZiBwb2ludHMgb2YgdGhlIG91dGVyIHBvbHlnb24uPFwvbGk+XHJcblx0PGxpPm48c3ViPm88XC9zdWI+IGxpbmVzIHdpdGggdHdvIGludGVnZXJzIGVhY2g6IHRoZSBjb29yZGluYXRlcyBvZiB0aGUgcG9pbnRzIG9mIHRoZSBvdXRlciBwb2x5Z29uIGluIGNvbnNlY3V0aXZlIG9yZGVyLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPkFsbCBjb29yZGluYXRlcyBoYXZlIGFic29sdXRlIHZhbHVlIG5vIGxhcmdlciB0aGFuIDEgMDAwLiBUaGUgcG9pbnRzIG9mIHRoZSBwb2x5Z29ucyBjYW4gYmUgZ2l2ZW4gaW4gZWl0aGVyIGNsb2Nrd2lzZSBvciBjb3VudGVyY2xvY2t3aXNlIG9yZGVyIGFuZCB0aGUgdHdvIHBvbHlnb25zIGRvIG5vdCBpbnRlcnNlY3Qgb3IgdG91Y2ggdGhlbXNlbHZlcyBvciBlYWNoIG90aGVyLiBUaGUgb3V0ZXIgcG9seWdvbiBlbmNsb3NlcyB0aGUgaW5uZXIgcG9seWdvbi48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5QZXIgdGVzdGNhc2U6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+T25lIGxpbmUgd2l0aCBhIGZsb2F0aW5nIHBvaW50IG51bWJlcjogdGhlIG1heGltYWwgcmFkaXVzIG9mIHRoZSB3aGl0ZSB3YXRlciByYWZ0cy4gVGhpcyBudW1iZXIgbXVzdCBoYXZlIGEgcmVsYXRpdmUgb3IgYWJzb2x1dGUgZXJyb3IgbGVzcyB0aGFuIDEwPHN1cD4mbWludXM7NjxcL3N1cD4uPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=