ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

USU Championship 2003

About     Problems     Submit solution     Judge status     Standings
Contest is over

G. Sailing Directions

Time limit: 3.0 second
Memory limit: 64 MB
Attention, attention! Moscow is speaking! All the radio stations are on air. We broadcast the urgent announcement.
Today the sea trials of the new supertanker “Oil industry worker” will take place. The new development of our scientists — the system “Sailing Directions” — will be world-wide demonstrated. This system provides an optimal control of the ship without a human in a square harbor. A ship (and all the ships have a triangle form) may move from the given start position to the final one among the other ships anchored in the harbor along the shortest distance. Everything necessary for the safe test was stipulated on the “Oil industry worker”: a thick steel sheeting; electronic control system; satellite communications with the complex of coordinates determination; and sensitive radar. But as usual meddled in a human element. Vovochka, the captain’s son, secretly stole to the ship just before the presentation, set down at the computer and decided to while away the time playing his favorite computer game. As a result a computer virus penetrated into the computer and it spoilt several functions of the program “Sailing Directions”. Now the ship can’t turn around its axis. You are to write a program that provides the shortest tanker route length to the given point.

Input

The first line consists of two integer numbers DX and DY — the dimensions of the harbor (0 < DX, DY < 108). Each of the lines 2-4 contain two integers — the tanker coordinates (remember that the “Oil industry worker” is triangle as all the ships). The fifth line contains a point where the tanker is to come in the end (namely its vertex described in the second input line). The sixth line consists of the integer N (the number of other ships in the harbor, 0 ≤ N ≤ 40). The next 3N lines contain those ships coordinates. All the coordinates are within the harbor. The harbor corner is the point of origin. The ships don’t intersect.

Output

the minimal length of the route rounded to three digits after a decimal point, or −1, if the “Oil industry worker” won’t be able to reach the final point because of the injuries in the navigation program.

Sample

inputoutput
2003 2003
20 50
10 30
30 30
140 60
1
80 1000
100 20
60 20
146.569

Notes

  • Harbor is rectangle with coordinates of corners (0,0), (DX,0), (DX,DY), (0,DY).
  • Ship may not sail through harbor borders.
  • Ships may touch each other and harbor borders.
Problem Author: Alexey Lakhtin
Problem Source: Ural State University championship, October 25, 2003
To submit the solution for this problem go to the Problem set: 1271. Sailing Directions