시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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+XHViYWE4XHViNGUwIFx1Yzg4Y1x1ZDQ1Y1x1Yzc1OCBcdWM4MDhcdWIzMTNcdWFjMTJcdWM3NDAgMTAwMCBcdWM3NzRcdWQ1NThcdWM3NzRcdWFjZTAsIFx1YjJlNFx1YWMwMVx1ZDYxNVx1Yzc1OCBcdWM4MTBcdWM3NDAgXHVjMmRjXHVhY2M0IFx1ZDYzOVx1Yzc0MCBcdWJjMThcdWMyZGNcdWFjYzQgXHViYzI5XHVkNWE1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViNDUwIFx1YWMxY1x1Yzc1OCBcdWIyZTRcdWFjMDFcdWQ2MTVcdWM3NDAgXHVjMTFjXHViODVjIFx1YWNiOVx1Y2U1OFx1YWM3MFx1YjA5OCBcdWI5Y2NcdWIwOThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LiBcdWQ1NmRcdWMwYzEgXHVjNjc4XHViZDgwIFx1YjJlNFx1YWMwMVx1ZDYxNVx1Yzc0MCBcdWIwYjRcdWJkODAgXHViMmU0XHVhYzAxXHVkNjE1XHVjNzQ0IFx1ZDNlY1x1ZDU2OFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4XHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0IFx1ZDI5Y1x1YmUwY1x1Yzc1OCBcdWNkNWNcdWIzMDAgXHVkMDZjXHVhZTMwXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4mbmJzcDtcdWMwYzFcdWIzMDBcL1x1YzgwOFx1YjMwMCBcdWM2MjRcdWNjMjhcdWFjMDAgMTBeLTYgXHViYmY4XHViOWNjXHVjNzc4IFx1YWNiZFx1YzZiMCBcdWM4MTVcdWIyZjVcdWM3M2NcdWI4NWMgXHVjYzk4XHViOWFjXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzY4OCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IldoaXRlIFdhdGVyIFJhZnRpbmciLCJkZXNjcmlwdGlvbiI6IjxwPllvdSBoYXZlIGJlZW4gaGlyZWQgYnkgYSBiaWcgdGhlbWUgcGFyayB0byBkZXNpZ24gYSBuZXcgYXR0cmFjdGlvbjogYSB3aGl0ZSB3YXRlciByYWZ0aW5nIHJpZGUuIFlvdSBhbHJlYWR5IGRlc2lnbmVkIHRoZSB0cmFjazsgaXQgaXMgYSByb3VuZCB0cmlwIHRoYXQgaXMgZGVzY3JpYmVkIGJ5IGFuIGlubmVyIGFuZCBhbiBvdXRlciBwb2x5Z29uLiBUaGUgc3BhY2UgaW4gYmV0d2VlbiB0aGUgdHdvIHBvbHlnb25zIGlzIHRoZSB0cmFjay48XC9wPlxyXG5cclxuPHA+WW91IHN0aWxsIG5lZWQgdG8gZGVzaWduIHRoZSByYWZ0cywgaG93ZXZlci4gSXQgaGFzIGJlZW4gZGVjaWRlZCB0aGF0IHRoZXkgc2hvdWxkIGJlIGNpcmN1bGFyLCBzbyB0aGF0IHRoZXkgY2FuIHNwaW4gZnJlZWx5IGFsb25nIHRoZSB0cmFjayBhbmQgaW5jcmVhc2UgdGhlIGZ1biBhbmQgZXhjaXRlbWVudCBvZiB0aGUgcmlkZS4gQmVzaWRlcyB0aGF0LCB0aGV5IHNob3VsZCBiZSBhcyBiaWcgYXMgcG9zc2libGUgdG8gZml0IHRoZSBtYXhpbXVtIG51bWJlciBvZiBwZW9wbGUsIGJ1dCB0aGV5IGNhbiZyc3F1bzt0IGJlIHRvbyBiaWcsIGZvciBvdGhlcndpc2UgdGhleSB3b3VsZCBnZXQgc3R1Y2sgc29tZXdoZXJlIG9uIHRoZSB0cmFjay48XC9wPlxyXG5cclxuPHA+V2hhdCBpcyB0aGUgbWF4aW11bSByYWRpdXMgb2YgdGhlIHJhZnRzIHNvIHRoYXQgdGhleSBjYW4gY29tcGxldGUgdGhlIHRyYWNrPzxcL3A+XHJcbiIsImlucHV0IjoiPHA+T24gdGhlIGZpcnN0IGxpbmUgb25lIHBvc2l0aXZlIG51bWJlcjogdGhlIG51bWJlciBvZiB0ZXN0Y2FzZXMsIGF0IG1vc3QgMTAwLiBBZnRlciB0aGF0IHBlciB0ZXN0Y2FzZTo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5PbmUgbGluZSB3aXRoIGFuIGludGVnZXIgbjxzdWI+aTxcL3N1Yj4gKDMgJmxlOyBuPHN1Yj5pPFwvc3ViPiAmbGU7IDEwMCk6IHRoZSBudW1iZXIgb2YgcG9pbnRzIG9mIHRoZSBpbm5lciBwb2x5Z29uLjxcL2xpPlxyXG5cdDxsaT5uPHN1Yj5pPFwvc3ViPiBsaW5lcyB3aXRoIHR3byBpbnRlZ2VycyBlYWNoOiB0aGUgY29vcmRpbmF0ZXMgb2YgdGhlIHBvaW50cyBvZiB0aGUgaW5uZXIgcG9seWdvbiBpbiBjb25zZWN1dGl2ZSBvcmRlci48XC9saT5cclxuXHQ8bGk+T25lIGxpbmUgd2l0aCBhbiBpbnRlZ2VyIG48c3ViPm88XC9zdWI+ICgzICZsZTsgbjxzdWI+bzxcL3N1Yj4gJmxlOyAxMDApOiB0aGUgbnVtYmVyIG9mIHBvaW50cyBvZiB0aGUgb3V0ZXIgcG9seWdvbi48XC9saT5cclxuXHQ8bGk+bjxzdWI+bzxcL3N1Yj4gbGluZXMgd2l0aCB0d28gaW50ZWdlcnMgZWFjaDogdGhlIGNvb3JkaW5hdGVzIG9mIHRoZSBwb2ludHMgb2YgdGhlIG91dGVyIHBvbHlnb24gaW4gY29uc2VjdXRpdmUgb3JkZXIuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+QWxsIGNvb3JkaW5hdGVzIGhhdmUgYWJzb2x1dGUgdmFsdWUgbm8gbGFyZ2VyIHRoYW4gMSAwMDAuIFRoZSBwb2ludHMgb2YgdGhlIHBvbHlnb25zIGNhbiBiZSBnaXZlbiBpbiBlaXRoZXIgY2xvY2t3aXNlIG9yIGNvdW50ZXJjbG9ja3dpc2Ugb3JkZXIgYW5kIHRoZSB0d28gcG9seWdvbnMgZG8gbm90IGludGVyc2VjdCBvciB0b3VjaCB0aGVtc2VsdmVzIG9yIGVhY2ggb3RoZXIuIFRoZSBvdXRlciBwb2x5Z29uIGVuY2xvc2VzIHRoZSBpbm5lciBwb2x5Z29uLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlBlciB0ZXN0Y2FzZTo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5PbmUgbGluZSB3aXRoIGEgZmxvYXRpbmcgcG9pbnQgbnVtYmVyOiB0aGUgbWF4aW1hbCByYWRpdXMgb2YgdGhlIHdoaXRlIHdhdGVyIHJhZnRzLiBUaGlzIG51bWJlciBtdXN0IGhhdmUgYSByZWxhdGl2ZSBvciBhYnNvbHV0ZSBlcnJvciBsZXNzIHRoYW4gMTA8c3VwPiZtaW51czs2PFwvc3VwPi48XC9saT5cclxuPFwvdWw+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d