Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

凸多角形柱工業都市

凸多角形柱工業都市 (Industrial Convex Pillar City, ICPC) はいくつかの凸多角形柱の形状をした建物からなる街である．あなたはこの街の中を現在地 S から目的地 T に向けて歩こうとしている．今日は日差しが強いので，出来る限りひなたを通らずに目的地へ向かいたい．あなたが立っている地点と太陽を一直線に結んだ線上に建物がある場合，あなたは建物の陰にいるので日差しを受けずにすむ．また，この街の建物の外周には全てひさしが付いているので，建物の外周に沿って歩いている間は，日が当たる縁に沿って歩いても日差しを受けることはない．あなたは建物の内部以外はこの街をどこでも自由に歩くことができる．

もっとも日差しを受けないように現在地から目的地まで歩いた時の，ひなたを歩く距離を出力するプログラムを作成しなさい．

  
図E1: 第1インプットの場合
  

  
図E2: 第2インプットの場合
  

  
図E3: 第3インプットの場合
  

Input

入力は複数のデータセットからなる．
データセットの個数は最大でも 30 個を超えない．
各データセットは次の形式で表される．

N
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
&theta; &phi;
Sx Sy Tx Ty

１行目の N は建物の数を表す．続く N 行は各建物の形状を指定する．NVi は i 番目の建物を上から見た多角形の頂点数，Hi は i 番目の建物の高さを表す．Xi, j と Yi, j は i 番目の建物を上から見た多角形の j 番目の頂点の x 座標と y 座標を表す．頂点は反時計回りの順で与えられる．全ての建物は上から見ると凸多角形であり，建物の内部に他の建物があったり，頂点や辺が他の多角形と重なったりすることはない．続く行には太陽の方向を表す &theta; と &phi; が与えられ，&theta; は太陽の向きを x の正の方向から反時計回りの角度で表し，&phi; は地平線からの太陽の仰角，すなわち太陽を見上げた時の視線の方向と地表面がなす角度を表す．ただし，太陽は無限遠にあり，移動中には位置を変えないものとする．続く行には現在地と目的地の座標， (Sx, Sy) と (Tx, Ty) が与えられる．

入力で与えられる数値は全て整数であり，以下の条件を満たす．

1 ≤ N ≤ 100
3 ≤ NVi ≤ 12
1 ≤ Hi ≤ 1,000
0 ≤ &theta; < 360
0 < &phi; < 90

座標は全て -1,000 以上 1,000 以下である．
現在地と目的地は異なり，どちらも建物の内部及び外周には存在しない．

入力の終わりは，１つのゼロからなる行で表される．

Output

各データセットについて，ひなたを歩く最短距離を１行に出力せよ．出力には 0.001 を超える絶対誤差があってはならない．

Sample Input

2
4 1 0 0 1 0 1 1 0 1
4 2 2 2 3 2 3 3 2 3
60 45
-1 -1 4 4
4
4 1 0 0 3 1 1 2 0 1
3 2 10 7 8 2 12 4
6 8 7 12 8 13 9 15 10 19 11 24 10 25
5 4 16 2 16 4 12 8 14 2 15 0
167 38
3 3 15 21
12
4 3 -8 -3 -9 -3 -9 -5 -8 -6
4 5 -4 -5 -7 -5 -7 -6 -5 -6
4 2 -4 1 -5 1 -5 -4 -4 -4
4 1 -1 1 -2 1 -2 -4 -1 -3
4 2 2 3 -1 3 -2 2 3 2
4 1 3 1 2 1 2 -3 3 -4
4 7 1 0 0 0 0 -1 1 -1
4 4 9 5 7 5 7 4 10 4
4 3 6 5 5 4 5 0 6 0
4 5 8 -1 5 -1 6 -2 8 -2
4 1 10 0 9 0 9 -2 10 -1
4 6 10 2 8 2 8 1 10 1
131 78
-10 10 10 -10
0

Output for Sample Input

1.93185
7.87174
20.86840


Sample input:
2
4 1 0 0 1 0 1 1 0 1
4 2 2 2 3 2 3 3 2 3
60 45
-1 -1 4 4
4
4 1 0 0 3 1 1 2 0 1
3 2 10 7 8 2 12 4
6 8 7 12 8 13 9 15 10 19 11 24 10 25
5 4 16 2 16 4 12 8 14 2 15 0
167 38
3 3 15 21
12
4 3 -8 -3 -9 -3 -9 -5 -8 -6
4 5 -4 -5 -7 -5 -7 -6 -5 -6
4 2 -4 1 -5 1 -5 -4 -4 -4
4 1 -1 1 -2 1 -2 -4 -1 -3
4 2 2 3 -1 3 -2 2 3 2
4 1 3 1 2 1 2 -3 3 -4
4 7 1 0 0 0 0 -1 1 -1
4 4 9 5 7 5 7 4 10 4
4 3 6 5 5 4 5 0 6 0
4 5 8 -1 5 -1 6 -2 8 -2
4 1 10 0 9 0 9 -2 10 -1
4 6 10 2 8 2 8 1 10 1
131 78
-10 10 10 -10
0


Sample output:
1.93185
7.87174
20.86840

Submission status: Accepted

Solution code:
from math import sin, cos, tan, radians
from heapq import heappush, heappop
import sys
readline = sys.stdin.readline
write = sys.stdout.write

def dot3(O, A, B):
    ox, oy = O; ax, ay = A; bx, by = B
    return (ax - ox) * (bx - ox) + (ay - oy) * (by - oy)
def cross3(O, A, B):
    ox, oy = O; ax, ay = A; bx, by = B
    return (ax - ox) * (by - oy) - (bx - ox) * (ay - oy)
def dist2(A, B):
    ax, ay = A; bx, by = B
    return (ax - bx) ** 2 + (ay - by) ** 2
def is_intersection(P0, P1, Q0, Q1):
    C0 = cross3(P0, P1, Q0)
    C1 = cross3(P0, P1, Q1)
    if C0 == C1 == 0:
        E0 = dot3(P0, P1, Q0)
        E1 = dot3(P0, P1, Q1)
        if not E0 < E1:
            E0, E1 = E1, E0
        return E0 <= dist2(P0, P1) and 0 <= E1
    D0 = cross3(Q0, Q1, P0)
    D1 = cross3(Q0, Q1, P1)
    return C0 * C1 <= 0 and D0 * D1 <= 0
def convex_hull(ps):
    qs = []
    n = len(ps)
    for p in ps:
        while len(qs) > 1 and cross3(qs[-1], qs[-2], p) >= 0:
            qs.pop()
        qs.append(p)
    t = len(qs)
    for i in range(n-2, -1, -1):
        p = ps[i]
        while len(qs) > t and cross3(qs[-1], qs[-2], p) >= 0:
            qs.pop()
        qs.append(p)
    return qs
def cross2(p, q):
    return p[0]*q[1] - p[1]*q[0]
def dot2(p, q):
    return p[0]*q[0] + p[1]*q[1]
def dist1(p):
    return p[0]**2 + p[1]**2
def segment_line_dist_d(x, p0, p1):
    z0 = (p1[0] - p0[0], p1[1] - p0[1])
    z1 = (x[0] - p0[0], x[1] - p0[1])
    if 0 <= dot2(z0, z1) <= dist1(z0):
        return cross2(z0, z1)**2 / dist1(z0)
    z2 = (x[0] - p1[0], x[1] - p1[1])
    return min(dist1(z1), dist1(z2))

def polygon_contain(x, ps):
    if len(ps) == 1:
        return 0
    pl = len(ps)
    return (
        all(cross3(ps[i-1], ps[i], x) > 0 for i in range(pl)) or
        all(cross3(ps[i-1], ps[i], x) < 0 for i in range(pl))
    )

def convex_polygon_contain(p0, qs):
    L = len(qs)
    if L < 3:
        return False
    left = 1; right = L
    x0, y0 = q0 = qs[0]
    while left+1 < right:
        mid = (left + right) >> 1
        if cross3(q0, p0, qs[mid]) <= 0:
            left = mid
        else:
            right = mid
    if left == L-1:
        left -= 1
    qi = qs[left]; qj = qs[left+1]
    v0 = cross3(q0, qi, qj)
    v1 = cross3(q0, p0, qj)
    v2 = cross3(q0, qi, p0)
    if v0 < 0:
        v1 = -v1; v2 = -v2
    return 0 <= v1 and 0 <= v2 and v1 + v2 <= v0

def convex_polygons_intersection(ps, qs):
    pl = len(ps); ql = len(qs)
    if pl == 1 or ql == 1:
        return 0
    i = j = 0
    while (i < pl or j < ql) and (i < 2*pl) and (j < 2*ql):
        px0, py0 = ps0 = ps[(i-1)%pl]; px1, py1 = ps1 = ps[i%pl]
        qx0, qy0 = qs0 = qs[(j-1)%ql]; qx1, qy1 = qs1 = qs[j%ql]

        if is_intersection(ps0, ps1, qs0, qs1):
            return 1

        ax = px1 - px0; ay = py1 - py0
        bx = qx1 - qx0; by = qy1 - qy0

        v = (ax*by - bx*ay)
        va = cross3(qs0, qs1, ps1)
        vb = cross3(ps0, ps1, qs1)

        if v == 0 and va < 0 and vb < 0:
            return 0
        if v == 0 and va == 0 and vb == 0:
            i += 1
        elif v >= 0:
            if vb > 0:
                i += 1
            else:
                j += 1
        else:
            if va > 0:
                j += 1
            else:
                i += 1
    return 0

def find_tangent(p0, qs):
    L = len(qs)
    d = L//3
    gx = (qs[0][0] + qs[d][0] + qs[2*d][0]) / 3
    gy = (qs[0][1] + qs[d][1] + qs[2*d][1]) / 3
    g = (gx, gy)
    ma = -1; mi = 2; k0 = 0; k1 = 0
    for i in range(L):
        v = cross3(p0, qs[i], g) / (dist2(p0, g) * dist2(p0, qs[i]))**.5
        if v > ma:
            k1 = i
            ma = v
        if v < mi:
            k0 = i
            mi = v
    return k0, k1

def tangent_polygon_dist(ps, qs):
    Lp = len(ps); Lq = len(qs)
    pi, qi = find_tangent(qs[0], ps)
    pj, qj = find_tangent(ps[0], qs)
    if qi < pi:
        qi += Lp
    if qj < pj:
        qj += Lq
    res = dist2(ps[pi], qs[pj])
    if pj < qj:
        for i in range(pi, qi+1):
            x = ps[i-Lp]
            for j in range(pj, qj+1):
                res = min(res, segment_line_dist_d(x, qs[(j-1)%Lq], qs[j-Lq]))
    if pi < qi:
        for j in range(pj, qj+1):
            x = qs[j-Lq]
            for i in range(pi, qi+1):
                res = min(res, segment_line_dist_d(x, ps[(i-1)%Lp], ps[i-Lp]))
    return res**.5

def polygons_dist(ps, qs):
    if (convex_polygons_intersection(ps, qs)
            or convex_polygon_contain(ps[0], qs)
            or convex_polygon_contain(qs[0], ps)):
        return 0
    return tangent_polygon_dist(ps, qs)

def solve():
    N = int(readline())
    if N == 0:
        return False
    P = [[] for i in range(N)]
    H = [0]*N
    for i in range(N):
        k, h, *ps = map(int, readline().split())
        H[i] = h
        Pi = P[i]
        for j in range(k):
            x, y = ps[2*j:2*j+2]
            Pi.append((x, y))
    theta, phi = map(int, readline().split())
    r_theta = radians(theta)
    r_phi = radians(90 - phi)
    dx = -cos(r_theta)*tan(r_phi)
    dy = -sin(r_theta)*tan(r_phi)
    sx, sy, tx, ty = map(int, readline().split())

    for i in range(N):
        Pi = P[i]
        hi = H[i]
        for j in range(len(Pi)):
            x, y = Pi[j]
            Pi.append((x + hi*dx, y + hi*dy))
        Pi.sort()
        P[i] = convex_hull(Pi)[:-1]
        #print(P[i])
    P.append([(sx, sy)])
    P.append([(tx, ty)])

    E = [[0]*(N+2) for i in range(N+2)]
    dist = [10**18]*(N+2)
    for i in range(N+2):
        for j in range(i+1, N+2):
            E[i][j] = E[j][i] = polygons_dist(P[i], P[j])
    que = [(0, N)]
    dist[N] = 0
    while que:
        cost, v = heappop(que)
        if dist[v] < cost:
            continue
        for w in range(N+2):
            n_cost = cost + E[v][w]
            if n_cost < dist[w]:
                dist[w] = n_cost
                heappush(que, (n_cost, w))
    print("%.16f" % dist[N+1])
    return True
while solve():
    ...