Syötteenä annetaan yhtenäinen alue tasossa, ja lista kyselypistepareja siten, että kaikki pisteet ovat alueen sisäpisteitä. Tehtävänäsi on laskea jokaiselle pisteparille lyhyimmän alueen sisällä kulkevan reitin pituus pisteiden välillä. Kuten edellisessä tehtävässä, aluetta rajaa yksi monikulmio ja lisäksi siinä on monikulmion muotoisia reikiä.

Syöte

Syötteen ensimmäisellä rivillä ovat luvut R, N ja Q: monikulmioiden lukumäärä, kaikkien monikulmioiden kulmapisteiden yhteismäärä ja kyselypisteparien lukumäärä. Seuraavaksi ilmoitetaan jokainen monikulmio. Monikulmio alkaa rivillä, jossa on monikulmion kulmapisteiden lukumäärä N_i, ja tämän jälkeen seuraa jokaisen kulmapisteen X- ja Y-koordinaatit, jokainen kulmapiste omalla rivillään. Monikulmioiden jälkeen ilmoitetaan Q kyselypisteparia, jokainen omalla rivillään muodossa X_1 Y_1 X_2 Y_2.

Ensimmäinen monikulmio on tasoalueen ulkoraja ja loput monikulmioista ovat tasoalueen reikiä. Ensimmäinen monikulmio on suunnistettu myötäpäivään ja loput vastapäivään. Mikään monikulmioista ei leikkaa itseään tai muita monikulmioita, eivätkä mitkään kolme kulmapistettä ole samalla suoralla.

Tuloste

Ilmoita jokaista kyselypisteparia kohden lyhyimmän reitin pituus omalla rivillään.

Rajat

• R \geq 1
• 3 \leq N \leq 4096
• 1 \leq Q \leq 20
• N_i \geq 3
• N_1 + N_2 + \ldots + N_R = N
• Koordinaatit ovat itseisarvoltaan enintään 10^9

Mainos

Edellisen tehtävän debuggaustyökalusta voi olla apua myös tässä tehtävässä, ks. http://www.cs.helsinki.fi/u/totalvit/vis/visgraph.html.

Esimerkki

Syöte:

2 7 2
4 
0 0
0 4
6 4
6 0
3
1 2
3 1
3 3
1 1 4 2
1 1 4 1

Tuloste:

3.414213562373095
3