Problem: Convex polygon pillar industrial city

The Industrial Convex Pillar City (ICPC) is a city of buildings in the shape of several convex polygonal columns. You are about to walk through this city from your current location S to your destination T. The sun is strong today, so I want to go to my destination without passing through the sun as much as possible. If the building is on a straight line connecting the point where you are standing and the sun, you are behind the building and will not be exposed to the sun. Also, since all the outer circumferences of the buildings in this city have eaves, while walking along the outer circumference of the buildings, even if you walk along the edge of the sun, you will not receive the sunlight. You are free to walk around the city anywhere except inside the building.

Create a program that outputs the walking distance of Hinata when walking from the current location to the destination so as not to receive the sun.

<image>

Figure E1: For the first input

<image>

Figure E2: For the second input

<image>

Figure E3: For the third input

Input

The input consists of multiple datasets. The maximum number of data sets does not exceed 30. Each dataset is represented in the following format.

> 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
> θ φ
> Sx Sy Tx Ty
>

N in the first line represents the number of buildings. The following N lines specify the shape of each building. NVi represents the number of vertices of the polygon when the i-th building is viewed from above, and Hi represents the height of the i-th building. Xi, j and Yi, j represent the x-coordinate and y-coordinate of the j-th vertex of the polygon when the i-th building is viewed from above. The vertices are given in counterclockwise order. All buildings are convex polygons when viewed from above, and there are no other buildings inside the building, and the vertices and sides do not overlap with other polygons. The following lines are given θ and φ, which represent the direction of the sun, θ represents the direction of the sun as a counterclockwise angle from the positive direction of x, and φ is the elevation angle of the sun from the horizon, that is, looking up at the sun. It represents the angle between the direction of the line of sight and the ground surface. However, the sun is at infinity and does not change its position during movement. The following lines are given the coordinates of the current location and destination, (Sx, Sy) and (Tx, Ty).

> All the numerical values ​​given by the input are integers and satisfy the following conditions.

> 1 ≤ N ≤ 100
> 3 ≤ NVi ≤ 12
> 1 ≤ Hi ≤ 1,000
> 0 ≤ θ <360
> 0 <φ <90

All coordinates are -1,000 or more and 1,000 or less. The current location and the destination are different, and neither exists inside or outside the building.

> The end of the input is represented by a single zero line.

> ### Output

For each dataset, output the shortest walking distance in Hinata on one line. The output must not have an absolute error greater than 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
Four
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
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





Example

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

1.93185
7.87174
20.86840

Solution (in JAVA):

Solution:
import java.awt.geom.Point2D;
import java.io.IOException;
import java.io.InputStream;
import java.util.*;
import java.util.function.BiFunction;
import java.util.function.Function;
import java.util.function.Supplier;

public class Main {
  final static int INF = 1 << 28;
  final static long LNF = 1L << 60;
  final static long MOD = 1_000_000_007;
  final static double EPS = 1e-6;
  final static double GOLDEN_RATIO = (1.0 + Math.sqrt(5)) / 2.0;
  Scanner sc = new Scanner(System.in);

  public static void main(String[] args) {
    new Main().run();
  }

  class P {
    double x;
    double y;

    P(double a, double b) {
      x = a;
      y = b;
    }
  }

  class Node {
    double dist;
    int index;
  }

  P kaiten(double theta, P p) {
    return new P(p.x * Math.cos(theta) - p.y * Math.sin(theta),
        p.x * Math.sin(theta) + p.y * Math.cos(theta));
  }

  double getKakudo(P v, P w) {
    double atom = Math.atan2(v.y, v.x);
    if (atom < 0) {
      atom = 2 * Math.PI + atom;
    }
    P next = kaiten(-atom, w);
    double theta = Math.atan2(next.y, next.x);
    if (theta <= 0) {
      return -theta;
    } else {
      return 2 * Math.PI - theta;
    }
  }

  ArrayList<LineSegment> totuho(ArrayList<P> arr) {
    ArrayList<P> sub = new ArrayList<>();
    double value = Double.MAX_VALUE;
    P siten = null;
    for (P p : arr) {
      if (p.x * 100000 - p.y < value) {
        value = p.x * 100000 - p.y;
        siten = p;
      }
    }
    sub.add(siten);
    P vec = new P(0, 1);
    P ite = siten;
    for (; ; ) {
      double min = Double.MAX_VALUE;
      P next = null;
      P wec = null;
      for (P p : arr) {
        if (p == ite) {
          continue;
        }
        double dx = p.x - ite.x;
        double dy = p.y - ite.y;
        P w = new P(dx, dy);
        double theta = getKakudo(vec, w);
        if (theta < min) {
          min = theta;
          next = p;
          wec = w;
        }
//        double cos = GeomUtils.dot(vec.x, vec.y, dx, dy)
//            / (GeomUtils.abs(vec.x, vec.y) * GeomUtils.abs(dx, dy));
//        double theta = Math.acos(cos);
//        double ccw = GeomUtils.ccw(ite.x, ite.y, ite.x + vec.x, ite.y + vec.y, p.x, p.y);
//        if (ccw + EPS > 0) {
//          theta = 2 * Math.PI - theta;
//        }
//        theta += EPS;
//        theta %= 2 * Math.PI;
//        if (theta < min) {
//          min = theta;
//          next = p;
//          wec = new P(dx, dy);
//        }
      }
      if (next == siten) {
        break;
      }
      if (ite != siten) {
        double dx = siten.x - ite.x;
        double dy = siten.y - ite.y;
        P w = new P(dx, dy);
        double theta = getKakudo(vec, w);
        if (Math.abs(min - theta) < EPS) {
          break;
        }
      }
      sub.add(next);
      ite = next;
      vec = wec;
    }
    ArrayList<LineSegment> ans = new ArrayList<>();
    int n = sub.size();
    for (int i = 0; i < n; ++i) {
      P p = sub.get(i);
      P q = sub.get((i + 1) % n);
      LineSegment l = new LineSegment(p.x, p.y, q.x, q.y);
      ans.add(l);
    }
    return ans;
  }

  ArrayList<LineSegment> p2ls(double x, double y) {
    ArrayList<LineSegment> ans = new ArrayList<>();
    ans.add(new LineSegment(x, y, x, y));
    return ans;
  }

  boolean isIn(ArrayList<LineSegment> list, double x, double y) {
    if (list.size() == 1) {
      return false;
    }
    boolean flag = true;
    for (LineSegment l : list) {
      double ccw = GeomUtils.ccw(l.x1, l.y1, l.x2, l.y2, x, y);
      flag &= ccw - EPS <= 0;
    }
    return flag;
  }

  double dist(ArrayList<LineSegment> a, ArrayList<LineSegment> b) {
    double min = Double.MAX_VALUE;
    for (LineSegment ite : a) {
      if (isIn(b, ite.x1, ite.y1)
          || isIn(b, ite.x2, ite.y2)) {
        return 0;
      }
    }
    for (LineSegment ite : b) {
      if (isIn(a, ite.x1, ite.y1)
          || isIn(a, ite.x2, ite.y2)) {
        return 0;
      }
    }
    for (LineSegment ite : b) {
      for (LineSegment jte : a) {
        double d = ite.distance(jte);
        min = Math.min(min, d);
      }
    }
    return min;
  }

  void run() {
    for (; ; ) {
      int n = ni();
      if (n == 0) {
        break;
      }
      ArrayList<ArrayList<P>> list = new ArrayList<>();
      int[] hs = new int[n];
      for (int i = 0; i < n; ++i) {
        int m = ni();
        hs[i] = ni();
        ArrayList<P> arr = new ArrayList<>();
        for (int j = 0; j < m; ++j) {
          int x = ni();
          int y = ni();
          arr.add(new P(x, y));
        }
        list.add(arr);
      }
      double theta = ni() * Math.PI / 180;
      double gyokaku = ni() * Math.PI / 180;
//      debug("kage::");
      for (int i = 0; i < n; ++i) {
//        debug("\t", i);
        ArrayList<P> kage = new ArrayList<>();
        ArrayList<P> arr = list.get(i);
        double nagasa = hs[i] / Math.tan(gyokaku);
        for (P p : arr) {
          double x = p.x + nagasa * Math.cos(theta + Math.PI);
          double y = p.y + nagasa * Math.sin(theta + Math.PI);
//          debug("\t\t", x, y);
          kage.add(new P(x, y));
        }
        arr.addAll(kage);
      }
      ArrayList<ArrayList<LineSegment>> takakukeis = new ArrayList<>();
//      debug("takakukei::");
      for (ArrayList<P> arr : list) {
//        debug("\t", takakukeis.size());
        takakukeis.add(totuho(arr));
        for (LineSegment l : takakukeis.get(takakukeis.size() - 1)) {
//          debug("\t\t", l.x1, l.y1);
        }
      }
      double sx = ni();
      double sy = ni();
      double tx = ni();
      double ty = ni();
      takakukeis.add(p2ls(sx, sy));
      takakukeis.add(p2ls(tx, ty));
      PriorityQueue<Node> queue = new PriorityQueue<>(Comparator.comparingDouble(a -> a.dist));
      Node atom = new Node();
      atom.dist = 0;
      atom.index = n;
      queue.add(atom);
      boolean[] done = new boolean[n + 2];
      double[] ans = new double[n + 2];
//      debug("daikusutora");
      while (queue.size() > 0) {
        Node node = queue.poll();
        if (done[node.index]) {
          continue;
        }
//        debug("\t", node.index, node.dist);
        done[node.index] = true;
        ans[node.index] = node.dist;
        for (int i = 0; i < n + 2; ++i) {
          if (i == node.index) {
            continue;
          }
          ArrayList<LineSegment> arr = takakukeis.get(i);
          double dist = dist(takakukeis.get(node.index), arr);
          Node next = new Node();
          next.index = i;
          next.dist = dist + node.dist;
//          debug("\t\t", next.index, dist, next.dist);
          queue.add(next);
        }
      }
      System.out.printf("%.5f\n", ans[n + 1]);
    }
  }

  int ni() {
    return Integer.parseInt(sc.next());
  }

  long nl() {
    return sc.nextLong();
  }

  double nd() {
    return Double.parseDouble(sc.next());
  }

  void debug(Object... os) {
    System.err.println(Arrays.deepToString(os));
  }

  /**
   * from http://gihyo.jp/dev/serial/01/geometry part 6
   */
  static class Line {
    double a;
    double b;
    double c;

    /**
     * ?????¬??¢??????????????????????????´??????????????????
     *
     * @param a x????????°
     * @param b y????????°
     * @param c ?????°???
     */
    Line(double a, double b, double c) {
      this.a = a;
      this.b = b;
      this.c = c;
    }

    /**
     * 2???(x1, y1), (x2, y2)???????????´??????????????????
     *
     * @param x1 1?????????x??§?¨?
     * @param y1 1?????????y??§?¨?
     * @param x2 2?????????x??§?¨?
     * @param y2 2?????????y??§?¨?
     * @return ??´???
     */
    static Line fromPoints(double x1, double y1, double x2, double y2) {
      double dx = x2 - x1;
      double dy = y2 - y1;
      return new Line(dy, -dx, dx * y1 - dy * x1);
    }

    /**
     * ?????????????????´?????¨??????????????????
     *
     * @param l ??´???
     * @return ?????????2??´?????????????????´??????null
     */
    Point2D getIntersectionPoint(Line l) {
      double d = a * l.b - l.a * b;
      if (d == 0.0) {
        return null;
      }
      double x = (b * l.c - l.b * c) / d;
      double y = (l.a * c - a * l.c) / d;
      return new Point2D.Double(x, y);
    }

    @Override
    public String toString() {
      return "a = " + a + ", b = " + b + ", c = " + c;
    }
  }

  static class Line1D {
    int x1;
    int x2;

    // [x1, x2) : ????????????
    Line1D(int x1, int x2) {
      this.x1 = x1;
      this.x2 = x2;
    }

    boolean isCross(Line1D l) {
      return isCross(l.x1, l.x2);
    }

    boolean isCross(int y1, int y2) {
      boolean ret = x1 < y2 && y1 < x2;
      assert ret == new LineSegment(x1, 0, x2, 0).intersects(new LineSegment(y1, 0, y2, 0));
      return ret;
    }
  }

  /**
   * from http://gihyo.jp/dev/serial/01/geometry part 6
   */
  static public class LineSegment {
    double x1;
    double y1;
    double x2;
    double y2;

    LineSegment(double x1, double y1, double x2, double y2) {
      this.x1 = x1;
      this.y1 = y1;
      this.x2 = x2;
      this.y2 = y2;
    }

    Line toLine() {
      return Line.fromPoints(x1, y1, x2, y2);
    }

    boolean intersects(Line l) {
      double t1 = l.a * x1 + l.b * y1 + l.c;
      double t2 = l.a * x2 + l.b * y2 + l.c;
      return t1 * t2 <= 0;
    }

    boolean intersects(LineSegment s) {
      return bothSides(s) && s.bothSides(this);
    }

    // s???????????????????????´????????????????????????????????????
    private boolean bothSides(LineSegment s) {
      double ccw1 = GeomUtils.ccw(x1, y1, s.x1, s.y1, x2, y2);
      double ccw2 = GeomUtils.ccw(x1, y1, s.x2, s.y2, x2, y2);
      if (ccw1 == 0 && ccw2 == 0) { // s??¨?????????????????´?????????????????´???
        // s???????????????1???????????????????????????????????????????????°???s??????????????¨??±?????¨?????????????????§
        // true?????????
        return internal(s.x1, s.y1) || internal(s.x2, s.y2);
      } else { // ????????\????????´???
        // CCW???????¬?????????°????????´??????true?????????
        return ccw1 * ccw2 <= 0;
      }
    }

    // (x, y)?????????????????????????????????????????????????????????
    private boolean internal(double x, double y) {
      // (x, y)????????????????????????????????????????????????????????\?????§????????°????????¨?????????
      return GeomUtils.dot(x1 - x, y1 - y, x2 - x, y2 - y) <= 0;
    }

    public Point2D getIntersectionPoint(Line l) {
      if (!intersects(l)) {
        return null; // ?????????????????´??????null?????????
      }
      return l.getIntersectionPoint(toLine());
    }

    public Point2D getIntersectionPoint(LineSegment s) {
      if (!intersects(s)) {
        return null; // ?????????????????´??????null?????????
      }
      return s.toLine().getIntersectionPoint(toLine());
    }

    /**
     * from : http://www.deqnotes.net/acmicpc/2d_geometry/lines#distance_between_line_segment_and_point
     */
    double distance(double x0, double y0) {
      // ???????????§??????
      if (GeomUtils.dot(x2 - x1, y2 - y1, x0 - x1, y0 - y1) < EPS) {
        return GeomUtils.abs(x0 - x1, y0 - y1);
      }
      if (GeomUtils.dot(x1 - x2, y1 - y2, x0 - x2, y0 - y2) < EPS) {
        return GeomUtils.abs(x0 - x2, y0 - y2);
      }
      // ??´?????¨???????????¢
      return Math.abs(GeomUtils.cross(x2 - x1, y2 - y1, x0 - x1, y0 - y1)) / GeomUtils.abs(x2 - x1, y2 - y1);
    }

    double distance(LineSegment l) {
      if (this.intersects(l)) {
        return 0.0;
      }
      double min = Double.MAX_VALUE;
      min = Math.min(min, distance(l.x1, l.y1));
      min = Math.min(min, distance(l.x2, l.y2));
      min = Math.min(min, l.distance(x1, y1));
      min = Math.min(min, l.distance(x2, y2));
      return min;
    }

    @Override
    public String toString() {
      return "(" + x1 + ", " + y1 + ") - (" + x2 + ", " + y2 + ")";
    }
  }

  /**
   * from http://gihyo.jp/dev/serial/01/geometry part 6
   */
  static class GeomUtils {
    // ??????
    static double cross(double x1, double y1, double x2, double y2) {
      return x1 * y2 - x2 * y1;
    }

    // ??????
    static double dot(double x1, double y1, double x2, double y2) {
      return x1 * x2 + y1 * y2;
    }

    // (x1, y1) -> (x2, y2) -> (x3, y3) ??¨?????????????????????????¨????????????´????????£?????????
    // ????¨????????????´???????????????????????´???????????´?????????????????????
    static double ccw(double x1, double y1, double x2, double y2,
                      double x3, double y3) {
      return cross(x2 - x1, y2 - y1, x3 - x2, y3 - y2);
    }

    static double ccw(Point2D p1, Point2D p2, Point2D p3) {
      return ccw(p1.getX(), p1.getY(), p2.getX(), p2.getY(), p3.getX(), p3.getY());
    }

    // ?????????????????????
    static double abs(double x, double y) {
      return Math.sqrt(x * x + y * y);
    }

    // ????§???¢???????????????
    // http://www.nttpc.co.jp/technology/number_algorithm.html
    static boolean isIn(ArrayList<LineSegment> list, double x, double y) {
      int wn = 0;
      for (LineSegment l : list) {
        if (l.y1 <= y && l.y2 > y) {
          double vt = (y - l.y1) / (l.y2 - l.y1);
          if (x < l.x1 + (vt * (l.x2 - l.x1))) {
            ++wn;
          }
        }
        if (l.y1 > y && l.y2 <= y) {
          double vt = (y - l.y1) / (l.y2 - l.y1);
          if (x < (l.x1 + (vt * (l.x2 - l.x1)))) {
            --wn;
          }
        }
      }
      return wn > 0;
    }
  }
}