Walk under a Scorching Sun
Time limit8sMemory limit512 MB
Given convex building footprints, sun angles, and road segments, find a route from S to T whose portion outside building shadows is as short as possible.
- Level
Hard8 of 10
- Topics
- Geometry, Shortest path, Graph
- Solved
- No attempts yet
Problem
Edward R. Nelson is visiting a strange town today for some task. The city is built on flat two-dimensional ground and has several vertical buildings, each of which forms a convex polygon when seen from above. In other words, the buildings are convex polygonal columns. Edward must travel from point to point by walking along the roads on the ground. The sun is scorching and it is very hot today, so he wants to walk as little as possible in the sunshine.
Given information about the buildings, roads, and direction of the sun, write a program that outputs the length of a route that minimizes the walking distance in the sunshine.
Input
The input consists of multiple data sets. Each data set is given in the following format:
N M
NV1 H1 X1,1 Y1,1 X1,2 Y1,2 . . . X1,NV1 Y1,NV1
...
NVN HN XN,1 YN,1 XN,2 YN,2 . . . XN,NVN YN,NVN
RX1,1 RY1,1 RX1,2 RY1,2
...
RXM,1 RYM,1 RXM,2 RYM,2
θ φ
SX SY TX TY
All numbers are integers. is the number of buildings (). is the number of roads (). is the number of vertices of the base of the -th building (). is the height of the -th building. and are the coordinates of the -th vertex of the base of the -th building. are the coordinates of the endpoints of the -th road. is the direction of the sun, given by a counterclockwise angle in degrees starting from the positive -axis (). is the elevation angle of the sun (). and are the coordinates of points and , respectively. All coordinates are between 0 and 1000.
The end of the input is a line with . This line should not be processed.
Points and are guaranteed to lie on roads. No shadow edge is parallel to a road. Assume the sun is infinitely far away and does not move while Edward walks.
Output
For each data set, print on one line the minimum length Edward must walk in the sunshine. The program may print any number of digits after the decimal point. The error must be at most 0.001.