Under construction

Still being built. Things may change

Walk under a Scorching Sun

Time limit8sMemory limit512 MB

Summary
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 SS to point TT 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. NN is the number of buildings (1≤N≤151 \le N \le 15). MM is the number of roads (1≤M≤151 \le M \le 15). NViNV_i is the number of vertices of the base of the ii-th building (3≤NVi≤103 \le NV_i \le 10). HiH_i is the height of the ii-th building. Xi,jX_{i,j} and Yi,jY_{i,j} are the coordinates of the jj-th vertex of the base of the ii-th building. RXk,1,RYk,1,RXk,2,RYk,2RX_{k,1}, RY_{k,1}, RX_{k,2}, RY_{k,2} are the coordinates of the endpoints of the kk-th road. θθ is the direction of the sun, given by a counterclockwise angle in degrees starting from the positive xx-axis (0≤θ<3600 \le θ < 360). φφ is the elevation angle of the sun (0<φ<900 < φ < 90). (SX,SY)(SX, SY) and (TX,TY)(TX, TY) are the coordinates of points SS and TT, respectively. All coordinates are between 0 and 1000.

The end of the input is a line with N=M=0N = M = 0. This line should not be processed.

Points SS and TT 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.

Examples1

  1. Example 1

    Input
    1 1
    4 10 0 0 10 0 10 10 0 10
    -5 -20 30 15
    135 45
    0 -15 15 0
    0 0
    
    Expected output
    11.213