시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 63 17 8 16.667%

문제

좀은 옷(천으로 된)을 좀먹고 사는 벌레이다. 한 마리의 좀이 천으로 된 옷감 위에 놓여있다. 좀은 매우 작기 때문에, 천의 크기는 무한한 것으로 가정한다. 또, 천의 곳곳에는 다른 재질의 옷감으로 기워져 있는 부분이 N군데 있다. 기워져 있는 부분은 항상 볼록다각형 모양을 이루고 있는데, 이러한 볼록다각형들이 서로 닿아 있거나 겹쳐져 있을 수도 있다.

이 좀은 어떤 특정한 위치(옷감 위의)로 이동하려 하는데, 옷감을 좀먹으며 이동해야 하기 때문에 천으로 된 부분만을 지나며 이동해야 한다. 다른 재질의 옷감으로 기울 때에는 천으로 된 실을 사용했기 때문에, 기워져 있는 부분의 테두리(볼록다각형의 각 변들)는 지날 수 있다고 가정하자. 만약 두 볼록다각형의 변이 맞닿아 있는 부분이 있다면, 이러한 부분 역시 지날 수 있다고 하자. 하지만 실제로 기워진 부분 위(볼록다각형의 내부)는 절대로 지날 수 없다.

좀이 목적지까지 이동할 때의 최소 거리를 구해내는 프로그램을 작성하시오.

입력

첫째 줄에 다섯 정수 N, X, Y, U, V가 주어진다. 이는 좀의 현재 위치가 (X, Y)이고, 이동하려는 곳이 (U, V)라는 의미이다. 다음 N개의 줄에는 기워진 부분들을 의미하는 볼록다각형이 주어진다. 각 줄에 처음에는 볼록다각형의 꼭짓점의 개수 M이 주어지고, 그 다음 M개의 점들의 x, y좌표가 차례로 주어진다. 모든 볼록다각형의 꼭짓점의 합은 300을 넘지 않으며, 모든 좌표는 -10,000이상 10,000이하의 정수이다.

출력

첫째 줄에 답을 출력한다. 절대/상대 오차는 10-3까지 허용한다. 만약 이동할 수 없다면 -1을 출력한다.

예제 입력 1

2 0 0 5 5
4 1 0 4 0 4 1 1 2
3 3 3 4 4 5 2

예제 출력 1

7.236
W3sicHJvYmxlbV9pZCI6IjIxMjUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM4ODAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1Yzg4MFx1Yzc0MCBcdWM2MzcoXHVjYzljXHVjNzNjXHViODVjIFx1YjQxYylcdWM3NDQgXHVjODgwXHViYTM5XHVhY2UwIFx1YzBhY1x1YjI5NCBcdWJjOGNcdWI4MDhcdWM3NzRcdWIyZTQuIFx1ZDU1YyBcdWI5YzhcdWI5YWNcdWM3NTggXHVjODgwXHVjNzc0IFx1Y2M5Y1x1YzczY1x1Yjg1YyBcdWI0MWMgXHVjNjM3XHVhYzEwIFx1YzcwNFx1YzVkMCBcdWIxOTNcdWM1ZWNcdWM3ODhcdWIyZTQuIFx1Yzg4MFx1Yzc0MCBcdWI5ZTRcdWM2YjAgXHVjNzkxXHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgXHVjYzljXHVjNzU4IFx1ZDA2Y1x1YWUzMFx1YjI5NCBcdWJiMzRcdWQ1NWNcdWQ1NWMgXHVhYzgzXHVjNzNjXHViODVjIFx1YWMwMFx1YzgxNVx1ZDU1Y1x1YjJlNC4gXHViNjEwLCBcdWNjOWNcdWM3NTggXHVhY2YzXHVhY2YzXHVjNWQwXHViMjk0IFx1YjJlNFx1Yjk3OCBcdWM3YWNcdWM5YzhcdWM3NTggXHVjNjM3XHVhYzEwXHVjNzNjXHViODVjIFx1YWUzMFx1YzZjY1x1YzgzOCBcdWM3ODhcdWIyOTQgXHViZDgwXHViZDg0XHVjNzc0IE5cdWFkNzBcdWIzNzAgXHVjNzg4XHViMmU0LiBcdWFlMzBcdWM2Y2NcdWM4MzggXHVjNzg4XHViMjk0IFx1YmQ4MFx1YmQ4NFx1Yzc0MCBcdWQ1NmRcdWMwYzEgXHViY2ZjXHViODVkXHViMmU0XHVhYzAxXHVkNjE1IFx1YmFhOFx1YzU5MVx1Yzc0NCBcdWM3NzRcdWI4ZThcdWFjZTAgXHVjNzg4XHViMjk0XHViMzcwLCBcdWM3NzRcdWI3ZWNcdWQ1NWMgXHViY2ZjXHViODVkXHViMmU0XHVhYzAxXHVkNjE1XHViNGU0XHVjNzc0IFx1YzExY1x1Yjg1YyBcdWIyZmZcdWM1NDQgXHVjNzg4XHVhYzcwXHViMDk4IFx1YWNiOVx1Y2NkMFx1YzgzOCBcdWM3ODhcdWM3NDQgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0IFx1Yzg4MFx1Yzc0MCBcdWM1YjRcdWI1YTQgXHVkMmI5XHVjODE1XHVkNTVjIFx1YzcwNFx1Y2U1OChcdWM2MzdcdWFjMTAgXHVjNzA0XHVjNzU4KVx1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NThcdWI4MjQgXHVkNTU4XHViMjk0XHViMzcwLCBcdWM2MzdcdWFjMTBcdWM3NDQgXHVjODgwXHViYTM5XHVjNzNjXHViYTcwIFx1Yzc3NFx1YjNkOVx1ZDU3NFx1YzU3YyBcdWQ1NThcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1Y2M5Y1x1YzczY1x1Yjg1YyBcdWI0MWMgXHViZDgwXHViZDg0XHViOWNjXHVjNzQ0IFx1YzljMFx1YjA5OFx1YmE3MCBcdWM3NzRcdWIzZDlcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWIyZTRcdWI5NzggXHVjN2FjXHVjOWM4XHVjNzU4IFx1YzYzN1x1YWMxMFx1YzczY1x1Yjg1YyBcdWFlMzBcdWM2YjggXHViNTRjXHVjNWQwXHViMjk0IFx1Y2M5Y1x1YzczY1x1Yjg1YyBcdWI0MWMgXHVjMmU0XHVjNzQ0IFx1YzBhY1x1YzZhOVx1ZDU4OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1YWUzMFx1YzZjY1x1YzgzOCBcdWM3ODhcdWIyOTQgXHViZDgwXHViZDg0XHVjNzU4IFx1ZDE0Y1x1YjQ1MFx1YjlhYyhcdWJjZmNcdWI4NWRcdWIyZTRcdWFjMDFcdWQ2MTVcdWM3NTggXHVhYzAxIFx1YmNjMFx1YjRlNClcdWIyOTQgXHVjOWMwXHViMGEwIFx1YzIxOCBcdWM3ODhcdWIyZTRcdWFjZTAgXHVhYzAwXHVjODE1XHVkNTU4XHVjNzkwLiBcdWI5Y2NcdWM1N2QgXHViNDUwIFx1YmNmY1x1Yjg1ZFx1YjJlNFx1YWMwMVx1ZDYxNVx1Yzc1OCBcdWJjYzBcdWM3NzQgXHViOWRlXHViMmZmXHVjNTQ0IFx1Yzc4OFx1YjI5NCBcdWJkODBcdWJkODRcdWM3NzQgXHVjNzg4XHViMmU0XHViYTc0LCBcdWM3NzRcdWI3ZWNcdWQ1NWMgXHViZDgwXHViZDg0IFx1YzVlZFx1YzJkYyBcdWM5YzBcdWIwYTAgXHVjMjE4IFx1Yzc4OFx1YjJlNFx1YWNlMCBcdWQ1NThcdWM3OTAuIFx1ZDU1OFx1YzljMFx1YjljYyBcdWMyZTRcdWM4MWNcdWI4NWMgXHVhZTMwXHVjNmNjXHVjOWM0IFx1YmQ4MFx1YmQ4NCBcdWM3MDQoXHViY2ZjXHViODVkXHViMmU0XHVhYzAxXHVkNjE1XHVjNzU4IFx1YjBiNFx1YmQ4MClcdWIyOTQgXHVjODA4XHViMzAwXHViODVjIFx1YzljMFx1YjBhMCBcdWMyMTggXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM4ODBcdWM3NzQgXHViYWE5XHVjODAxXHVjOWMwXHVhZTRjXHVjOWMwIFx1Yzc3NFx1YjNkOVx1ZDU2MCBcdWI1NGNcdWM3NTggXHVjZDVjXHVjMThjIFx1YWM3MFx1YjlhY1x1Yjk3YyBcdWFkNmNcdWQ1NzRcdWIwYjRcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViMmU0XHVjMTJmIFx1YzgxNVx1YzIxOCBOLCBYLCBZLCBVLCBWXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0XHViMjk0IFx1Yzg4MFx1Yzc1OCBcdWQ2MDRcdWM3YWMgXHVjNzA0XHVjZTU4XHVhYzAwIChYLCBZKVx1Yzc3NFx1YWNlMCwgXHVjNzc0XHViM2Q5XHVkNTU4XHViODI0XHViMjk0IFx1YWNmM1x1Yzc3NCAoVSwgVilcdWI3N2NcdWIyOTQgXHVjNzU4XHViYmY4XHVjNzc0XHViMmU0LiBcdWIyZTRcdWM3NGMgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhZTMwXHVjNmNjXHVjOWM0IFx1YmQ4MFx1YmQ4NFx1YjRlNFx1Yzc0NCBcdWM3NThcdWJiZjhcdWQ1NThcdWIyOTQgXHViY2ZjXHViODVkXHViMmU0XHVhYzAxXHVkNjE1XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1YzkwNFx1YzVkMCBcdWNjOThcdWM3NGNcdWM1ZDBcdWIyOTQgXHViY2ZjXHViODVkXHViMmU0XHVhYzAxXHVkNjE1XHVjNzU4IFx1YWYyZFx1YzlkM1x1YzgxMFx1Yzc1OCBcdWFjMWNcdWMyMTggTVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWFjZTAsIFx1YWRmOCBcdWIyZTRcdWM3NGMgTVx1YWMxY1x1Yzc1OCBcdWM4MTBcdWI0ZTRcdWM3NTggeCwgeVx1Yzg4Y1x1ZDQ1Y1x1YWMwMCBcdWNjMjhcdWI4NDBcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWJhYThcdWI0ZTAgXHViY2ZjXHViODVkXHViMmU0XHVhYzAxXHVkNjE1XHVjNzU4IFx1YWYyZFx1YzlkM1x1YzgxMFx1Yzc1OCBcdWQ1NjlcdWM3NDAgMzAwXHVjNzQ0IFx1YjExOFx1YzljMCBcdWM1NGFcdWM3M2NcdWJhNzAsIFx1YmFhOFx1YjRlMCBcdWM4OGNcdWQ0NWNcdWIyOTQgLTEwLDAwMFx1Yzc3NFx1YzBjMSAxMCwwMDBcdWM3NzRcdWQ1NThcdWM3NTggXHVjODE1XHVjMjE4XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViMmY1XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVjODA4XHViMzAwXC9cdWMwYzFcdWIzMDAgXHVjNjI0XHVjYzI4XHViMjk0IDEwPHN1cD4tMzxcL3N1cD5cdWFlNGNcdWM5YzAgXHVkNWM4XHVjNmE5XHVkNTVjXHViMmU0LiBcdWI5Y2NcdWM1N2QgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YzIxOCBcdWM1YzZcdWIyZTRcdWJhNzQgLTFcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjIxMjUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJNb3RoeSIsImRlc2NyaXB0aW9uIjoiPHA+TW90aHkgaXMgYSBzbWFsbCBtb3RoLiBNb3RoeSBhbmQgaGlzIG1vdGhlciBhcmUgcGxhY2VkIG9uIGEgdmVyeSBvbGQgcGFpciBvZiBqZWFucy4gQmVjYXVzZSB0aGUgamVhbnMgYXJlIHZlcnkgb2xkIHRoZXkgYXJlIGNvdmVyZWQgd2l0aCBwYXRjaGVzLiBTb21ldGltZXMgdGhlIHBhdGNoZXMgb3ZlcmxhcCBlYWNoIG90aGVyLiBFdmVyeSBwYXRjaCBpcyBhIGNvbnZleCBwb2x5Z29uIGFuZCBpcyBtYWRlIGJ5IHNvbWUgbWF0ZXJpYWwgZGlmZmVyZW50IGZyb20gY290dG9uLiBNb3RoeSB3YW50cyB0byBnbyB0byBoaXMgbW90aGVyIGluIHRoZSBmYXN0ZXN0IHBvc3NpYmxlIHdheS4gSGUgY2Fubm90IG1vdmUgd2l0aG91dCBlYXRpbmcgYW5kIGJlY2F1c2Ugb2YgaGlzIGFnZSBoZSBjYW5ub3QgZWF0IGFueXRoaW5nIGV4Y2VwdCBqZWFucyBhbmQgY290dG9uIHRocmVhZC4gRGVzcGl0ZSBoaXMgYWdlIE1vdGh5IGlzIHZlcnkgaW50ZWxsaWdlbnQsIGhlIGNhbiBtb3ZlIGZvbGxvd2luZyBwcmVjaXNlIGNvb3JkaW5hdGVzIGJ1dCBoZSBpcyB1bmFibGUgdG8gY29tcHV0ZSB0aGVtLiBXcml0ZSBhIHByb2dyYW0gdGhhdCBjYWxjdWxhdGVzIHRoZSBsZW5ndGggb2YgdGhlIG1pbmltYWwgcGF0aCBmcm9tIHRoZSBwb3NpdGlvbiBvZiBNb3RoeSB0byB0aGUgcG9zaXRpb24gb2YgaGlzIG1vdGhlci4gTW90aHkgbXVzdCBiZSBhYmxlIHRvIHBhc3MgdGhyb3VnaCB0aGlzIHBhdGguIENvbnNpZGVyIHRoYXQgdGhlIHBhaXIgb2Ygb2xkIGplYW5zIGlzIHBsYWNlZCBvbiBhIHBsYW5lIHN1cmZhY2UgYW5kIGlzIGJpZyBlbm91Z2guIE1vdGh5IGNhbiBtb3ZlIG9ubHkgYXQgdGhlIHN1cmZhY2Ugb2YgdGhlIGplYW5zIGJlY2F1c2UgaGUgaXMgbm90IGJpZyBlbm91Z2ggdG8gcGVuZXRyYXRlIHRocm91Z2ggdGhlbS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+QmVjYXVzZSBNb3RoeSBpcyBzbyBzbWFsbCBoZSBzaG91bGQgYmUgY29uc2lkZXJlZCBhcyBhIHBvaW50LiBNb3RoeSBhbHNvIGNhbiBtb3ZlIG9uIHRoZSBlZGdlcyBvZiBhbnkgb2YgdGhlIHBhdGNoZXMgYmVjYXVzZSB0aGV5IGFyZSBzZXdlZCB3aXRoIGNvdHRvbiB0aHJlYWRzLiBNb3RoeSBjYW4gbW92ZSBvbiBjb21tb24gZWRnZXMgYnV0IGNhbm5vdCBiZSBvbiB0b3Agb2YgYW55IHBhdGNoLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgYSBzaW5nbGUgaW50ZWdlciBUIGluZGljYXRpbmcgdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzLiBFYWNoIHRlc3QgY2FzZSBzdGFydHMgd2l0aCBudW1iZXIgTiBvZiBwYXRjaGVzLCBhbmQgZm91ciBpbnRlZ2VyIG51bWJlcnMgJm5kYXNoOyB0aGUgY29vcmRpbmF0ZXMgWCBhbmQgWSBvZiBNb3RoeSZyc3F1bztzIHBvc2l0aW9uIGFuZCBjb29yZGluYXRlcyBVIGFuZCBWIG9mIGhpcyBtb3RoZXImcnNxdW87cyBwb3NpdGlvbiwgc2VwYXJhdGVkIGJ5IHdoaXRlIHNwYWNlcyAoLTEwMDAwICZsZTsgWCwgWSwgVSwgViAmbGU7IDEwMDAwKS4gRWFjaCBwYXRjaCBpcyBkZXNjcmliZWQgb24gYSBzZXBhcmF0ZSBsaW5lIHN0YXJ0aW5nIHdpdGggdGhlIG51bWJlciBvZiB2ZXJ0aWNlcyBhbmQgZm9sbG93ZWQgYnkgYSBwYWlyIG9mIGludGVnZXIgY29vcmRpbmF0ZXMgKC0xMDAwMCAmbGU7IFhpLCBZaSAmbGU7IDEwMDAwKSBmb3IgZWFjaCBvZiB0aGUgdmVydGljZXMgb2YgdGhlIHBhdGNoLCBzZXBhcmF0ZWQgYnkgd2hpdGUgc3BhY2VzLiBUaGUgdG90YWwgbnVtYmVyIG9mIHZlcnRpY2VzIG9mIHBvbHlnb25zIHdpbGwgbm90IGV4Y2VlZCAzMDAuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggb2YgdGhlIHRlc3QgY2FzZXMgcHJvZ3JhbSBoYXMgdG8gb3V0cHV0IG9uIGEgc2VwYXJhdGUgbGluZSB0aGUgbGVuZ3RoIG9mIHRoZSBzaG9ydGVzdCBwYXRoIGJldHdlZW4gTW90aHkgYW5kIGhpcyBtb3RoZXIuIFRoZSByZXN1bHQgc2hvdWxkIGJlIHJvdW5kZWQgdG8gMyBkaWdpdHMgYWZ0ZXIgdGhlIGRlY2ltYWwgcG9pbnQuIFRoZSBwcm9ncmFtIGhhcyB0byBvdXRwdXQgJm5kYXNoOzEgaWYgTW90aHkgY2Fubm90IHJlYWNoIGhpcyBtb3RoZXIuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d