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 CPP):

Solution:
#include<iostream>
#include<cstdio>
#include<vector>
#include<complex>
#include<algorithm>
#include<deque>
#include<cstring>
#include<cassert>
#include<climits>
#include<map>
#include<queue>
#include<set>
#include<unordered_set>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define EPS (1e-8)
#define equals(a,b) (fabs((a)-(b))<EPS)
#define COUNTER_CLOCKWISE 1
#define CLOCKWISE -1 
#define ONLINE_BACK 2
#define ONLINE_FRONT -2
#define ON_SEGMENT 0

using namespace std;

// -- BEGIN --
class Point{
public:
  double x,y;

  Point(double x = 0,double y = 0): x(x),y(y){}

  Point operator + (Point p){return Point(x+p.x,y+p.y);}
  Point operator - (Point p){return Point(x-p.x,y-p.y);}
  Point operator * (double a){return Point(a*x,a*y);}
  Point operator / (double a){return Point(x/a,y/a);}
  Point operator * (Point a){ return Point(x * a.x - y * a.y, x * a.y + y * a.x); }

  bool operator < (const Point& p) const{ return !equals(x,p.x)?x<p.x:(!equals(y,p.y)&&y<p.y); }

  bool operator == (const Point& p)const{ return fabs(x-p.x) < EPS && fabs(y-p.y) < EPS; }

};

struct Segment{
  Point p1,p2;
  Segment(Point p1 = Point(),Point p2 = Point()):p1(p1),p2(p2){}
  bool operator <  (const Segment& s) const { return ( p2 == s.p2 ) ? p1 < s.p1 : p2 < s.p2; }
  bool operator == (const Segment& s) const { return ( s.p1 == p1 && s.p2 == p2 ) || ( s.p1 == p2 && s.p2 == p1 ); }

};

typedef Point Vector;
typedef Segment Line;
typedef vector<Point> Polygon;

ostream& operator << (ostream& os,const Point& a){ return os << "(" << a.x << "," << a.y << ")"; }

ostream& operator << (ostream& os,const Segment& a){ return os << "( " << a.p1 << " , " << a.p2 << " )"; }

double dot(Point a,Point b){ return a.x*b.x + a.y*b.y; }

double cross(Point a,Point b){ return a.x*b.y - a.y*b.x; }

double norm(Point a){ return a.x*a.x+a.y*a.y; }

double abs(Point a){ return sqrt(norm(a)); }

//rad ????§???????????????¢?????§?????????????????¨
Point rotate(Point a,double rad){ return Point(cos(rad)*a.x - sin(rad)*a.y,sin(rad)*a.x + cos(rad)*a.y); }

// ??????????????¢????????????
double toRad(double agl){ return agl*M_PI/180.0; }

// a => prev, b => cur, c=> next
// prev ?????? cur ????????£??? next ????????????????§????????±???????
double getArg(Point a,Point b,Point c){
  double arg1 = atan2(b.y-a.y,b.x-a.x);
  double arg2 = atan2(c.y-b.y,c.x-b.x);
  double arg = fabs( arg1 - arg2 );
  while( arg > M_PI ) arg -= 2.0 * M_PI;
  return fabs(arg);
}

int ccw(Point p0,Point p1,Point p2){
  Point a = p1-p0;
  Point b = p2-p0;
  if(cross(a,b) > EPS)return COUNTER_CLOCKWISE;
  if(cross(a,b) < -EPS)return CLOCKWISE;
  if(dot(a,b) < -EPS)return ONLINE_BACK;
  if(norm(a) < norm(b))return ONLINE_FRONT;
  return ON_SEGMENT;
}

Polygon andrewScan(Polygon s) {
  Polygon u,l;
  if((int)s.size() < 3)return s;

  sort(s.begin(),s.end());

  u.push_back(s[0]);
  u.push_back(s[1]);
  l.push_back(s[s.size()-1]);
  l.push_back(s[s.size()-2]);

  for(int i=2;i<(int)s.size();i++) {
    for(int n=(int)u.size();n >= 2 && ccw(u[n-2],u[n-1],s[i]) != CLOCKWISE; n--) u.pop_back();
    u.push_back(s[i]);
  }

  for(int i=(int)s.size()-3; i>=0 ; i--) {
    for(int n=(int)l.size(); n >= 2 && ccw(l[n-2],l[n-1],s[i]) != CLOCKWISE; n--) l.pop_back();
    l.push_back(s[i]);
  }

  reverse(l.begin(),l.end());

  for(int i = (int)u.size()-2; i >= 1; i--) l.push_back(u[i]);

  return l;
}


//cross product of pq and pr
double cross3p(Point p,Point q,Point r) { return (r.x-q.x) * (p.y -q.y) - (r.y - q.y) * (p.x - q.x); }
  
//returns true if point r is on the same line as the line pq
bool collinear(Point p,Point q,Point r) { return fabs(cross3p(p,q,r)) < EPS; }
  
//returns true if point t is on the left side of line pq
bool ccwtest(Point p,Point q,Point r){
  return cross3p(p,q,r) > 0; //can be modified to accept collinear points
}
 
bool onSegment(Point p,Point q,Point r){
  return collinear(p,q,r) && equals(sqrt(pow(p.x-r.x,2)+pow(p.y-r.y,2)) + sqrt(pow(r.x-q.x,2) + pow(r.y-q.y,2) ),sqrt(pow(p.x-q.x,2)+pow(p.y-q.y,2)) ) ;
}
  

bool isConvex(vector<Point> p) {
  int sz = (int)p.size();
  if(sz < 3)return false;//boundary case, we treat a point or a line as not convex
  bool isLeft = ccwtest(p[0],p[1],p[2]);
  for(int i=1; i<(int)p.size();i++)
    if(ccwtest(p[i],p[(i+1)%sz],p[(i+2)%sz]) != isLeft) return false;
  return true;
}


double angle(Point a,Point b,Point c) {
  double ux = b.x - a.x, uy = b.y - a.y;
  double vx = c.x - a.x, vy = c.y - a.y;
  return acos((ux*vx + uy*vy)/sqrt((ux*ux + uy*uy) * (vx*vx + vy*vy)));
}  
  
//????§???¢poly?????????????????????????????????p????????¨??????????????????????????????  
bool inPolygon(Polygon &poly,Point p){
  if((int)poly.size() == 0)return false;
  rep(i,(int)poly.size()) if(onSegment(poly[i],poly[(i+1)%poly.size()],p))return true;
  double sum = 0;
  for(int i=0; i < (int)poly.size() ;i++) {
    if( equals(cross(poly[i]-p,poly[(i+1)%poly.size()]-p),0.0) ) continue; // ????????????????????¨angle???nan?????????sum???nan??????????????¬
    if( cross3p(p,poly[i],poly[(i+1)%poly.size()]) < 0 ) sum -= angle(p,poly[i],poly[(i+1)%poly.size()]);
    else                                                 sum += angle(p,poly[i],poly[(i+1)%poly.size()]);
  }
  // ?????????????????????????????????????????¨?????????????????§??\????????????????????? 
  const double eps = 1e-5;
  return (fabs(sum - 2*M_PI) < eps || fabs(sum + 2*M_PI) < eps);
}  


bool intersectLL(Line l, Line m) {
  return abs(cross(l.p2-l.p1, m.p2-m.p1)) > EPS || // non-parallel
         abs(cross(l.p2-l.p1, m.p1-l.p1)) < EPS;   // same line
}
bool intersectLS(Line l, Line s) {
  return cross(l.p2-l.p1, s.p1-l.p1)*       // s[0] is left of l
         cross(l.p2-l.p1, s.p2-l.p1) < EPS; // s[1] is right of l
}
bool intersectLP(Line l,Point p) {
  return abs(cross(l.p2-p, l.p1-p)) < EPS;
}
bool intersectSS(Line s, Line t) {
  return ccw(s.p1,s.p2,t.p1)*ccw(s.p1,s.p2,t.p2) <= 0 &&
         ccw(t.p1,t.p2,s.p1)*ccw(t.p1,t.p2,s.p2) <= 0;
}
bool intersectSP(Line s, Point p) {
  return abs(s.p1-p)+abs(s.p2-p)-abs(s.p2-s.p1) < EPS; // triangle inequality
}

Point projection(Line l,Point p) {
  double t = dot(p-l.p1, l.p1-l.p2) / norm(l.p1-l.p2);
  return l.p1 + (l.p1-l.p2)*t;
}
Point reflection(Line l,Point p) {
  return p + (projection(l, p) - p) * 2;
}
double distanceLP(Line l, Point p) {
  return abs(p - projection(l, p));
}
double distanceLL(Line l, Line m) {
  return intersectLL(l, m) ? 0 : distanceLP(l, m.p1);
}

double distanceLS(Line l, Line s) {
  if (intersectLS(l, s)) return 0;
  return min(distanceLP(l, s.p1), distanceLP(l, s.p2));
}
double distanceSP(Line s, Point p) {
  Point r = projection(s, p);
  if (intersectSP(s, r)) return abs(r - p);
  return min(abs(s.p1 - p), abs(s.p2 - p));
}

double distanceSS(Line s, Line t) {
  if (intersectSS(s, t)) return 0;
  return min(min(distanceSP(s, t.p1), distanceSP(s, t.p2)),
             min(distanceSP(t, s.p1), distanceSP(t, s.p2)));
}

Point crosspoint(Line l,Line m){
  double A = cross(l.p2-l.p1,m.p2-m.p1);
  double B = cross(l.p2-l.p1,l.p2-m.p1);
  if(abs(A) < EPS && abs(B) < EPS){
    vector<Point> vec;
    vec.push_back(l.p1),vec.push_back(l.p2),vec.push_back(m.p1),vec.push_back(m.p2);
    sort(vec.begin(),vec.end());
    assert(vec[1] == vec[2]); //???????????°??????????????????
    return vec[1];
    //return m.p1;
  }
  if(abs(A) < EPS)assert(false);
  return m.p1 + (m.p2-m.p1)*(B/A);
}



// -- END -- 

const bool debug = false;

struct Edge {
  int dst;
  double cost;
};

bool LT(double a,double b) { return !equals(a,b) && a < b; }
bool LTE(double a,double b) { return equals(a,b) || a < b; }

int N,VN[110];
double Hs[110];
Polygon polies[110];
Point ep[2];

bool check(Segment &seg,int skip1=-1,int skip2=-1) {
  rep(i,N) {
    if( i == skip1 || i == skip2 ) continue;
    rep(j,VN[i]) {
      Segment ururu_beam = Segment(polies[i][j],polies[i][(j+1)%VN[i]]);
      if( equals(cross(seg.p1-seg.p2,ururu_beam.p1-ururu_beam.p2),0) ) continue;
      if( intersectSS(seg,ururu_beam) ) return false;
    }
  }
  return true;
}

Segment nearestSS(Segment &seg1,Segment &seg2) {
  Segment seg = Segment(seg1.p1,seg2.p1);
  double mini = abs(seg1.p1-seg2.p1);
  /*
  if( LT(abs(seg1.p1-seg2.p2),mini) ) {
    mini = abs(seg1.p1-seg2.p2);
    seg = Segment(seg1.p1,seg2.p2);
  }
  if( LT(abs(seg1.p2-seg2.p1),mini) ) {
    mini = abs(seg1.p2-seg2.p1);
    seg = Segment(seg1.p2,seg2.p1);
  }
  if( LT(abs(seg1.p2-seg2.p2),mini) ) {
    mini = abs(seg1.p2-seg2.p2);
    seg = Segment(seg1.p2,seg2.p2);
  }
  */
  Point proj = projection(seg2,seg1.p1);
  if( onSegment(seg2.p1,seg2.p2,proj) && LT(abs(seg1.p1-proj),mini) ) {
    mini = abs(seg1.p1-proj);
    seg = Segment(seg1.p1,proj);
  }
  proj = projection(seg2,seg1.p2);
  if( onSegment(seg2.p1,seg2.p2,proj) && LT(abs(seg1.p2-proj),mini) ) {
    mini = abs(seg1.p2-proj);
    seg = Segment(seg1.p2,proj);
  }
  proj = projection(seg1,seg2.p1);
  if( onSegment(seg1.p1,seg1.p2,proj) && LT(abs(seg2.p1-proj),mini) ) {
    mini = abs(seg2.p1-proj);
    seg = Segment(seg2.p1,proj);
  }
  proj = projection(seg1,seg2.p2);
  if( onSegment(seg1.p1,seg1.p2,proj) && LT(abs(seg2.p2-proj),mini) ) {
    mini = abs(seg2.p2-proj);
    seg = Segment(seg2.p2,proj);
  }
  return seg;
}

struct Data {
  int cur;
  double w;
  bool operator < ( const Data &data ) const {
    if( !equals(w,data.w) ) return LT(data.w,w);
    return cur > data.cur;
  }
};

vector<Edge> G[110];
double dijkstra(int V) {
  vector<double> mini(V,1e8);
  mini[0] = 0;
  priority_queue<Data> Q;
  Q.push((Data){0,0});
  while( !Q.empty() ) {
    Data data = Q.top(); Q.pop();
    if( data.cur == 1 ) return data.w;
    rep(i,(int)G[data.cur].size()) {
      Edge &e = G[data.cur][i];
      if( LT(data.w+e.cost,mini[e.dst]) ) {
	mini[e.dst] = data.w+e.cost;
	Q.push((Data){e.dst,mini[e.dst]});
      }
    }
  }
  return mini[1];
}

void compute(int N,double theta,double phi) {
  double ans = abs(ep[0]-ep[1]);
  // ??±?????????????????´????????????
  rep(i,N) {
    vector<Point> ps;
    Vector v = Vector(cos(theta),sin(theta));
    rep(j,VN[i]) {
      ps.push_back(polies[i][j]);
      ps.push_back(polies[i][j]-v*Hs[i]/tan(phi));
    }
    polies[i] = andrewScan(ps);
    VN[i] = (int)polies[i].size();
    
    if( debug ) {
      puts("");
      cout << i << "-th polygon" << endl;
      rep(j,(int)polies[i].size()) {
	cout << polies[i][j] << endl;
      }
    }

  }
  
  // ?§??????????+??±?????????????????´?????????????????§?§??????§??????????????§??????????????±??????????????¢????±??????°?????????
  rep(i,N+2) G[i].clear();
  rep(i,2) { //?§??????????????????±??????????????´??????????????¢
    rep(j,N) {
      if( inPolygon(polies[j],ep[i]) ) {
	G[i].push_back((Edge){2+j,0});
	G[2+j].push_back((Edge){i,0});
      } else {
	double mini = 1e8;

	rep(k,VN[j]) {
	  Segment seg = Segment(ep[i],polies[j][k]);
	  if( LTE(ans,abs(seg.p1-seg.p2)) ) continue;
	  if( LT(abs(seg.p1-seg.p2),mini) && check(seg,j) ) {
	    mini = abs(seg.p1-seg.p2);
	  }
	}
	rep(k,VN[j]) {
	  Point p = projection(Line(polies[j][k],polies[j][(k+1)%VN[j]]),ep[i]);
	  if( !onSegment(polies[j][k],polies[j][(k+1)%VN[j]],p) ) continue;
	  Segment seg = Segment(ep[i],p);
	  if( LTE(ans,abs(seg.p1-seg.p2)) ) continue;
	  if( LT(abs(seg.p1-seg.p2),mini) && check(seg,j) ) {
	    mini = abs(seg.p1-seg.p2);
	  }
	}
	//if( !equals(mini,1e8) ) {
	if( LT(mini,ans) ) {
	  G[i].push_back((Edge){2+j,mini});
	  G[2+j].push_back((Edge){i,mini});
	}
      }
    }
  }
  rep(i,N) { //??±??????????????´???i????????±??????????????´???j???????????¢
    REP(j,i+1,N) {
      double mini = 1e8;
      
      rep(k,VN[i]) {
	Segment seg1 = Segment(polies[i][k],polies[i][(k+1)%VN[i]]);
	rep(l,(int)polies[j].size()) {
	  Segment seg2 = Segment(polies[j][l],polies[j][(l+1)%VN[j]]);
	  
	  if( equals(cross(seg1.p1-seg1.p2,seg2.p1-seg2.p2),0.0) && ( onSegment(seg1.p1,seg1.p2,seg2.p1) || onSegment(seg1.p1,seg1.p2,seg2.p2) )  ) {
	    mini = 0;
	    goto Skip;
	  } else if( !equals(cross(seg1.p1-seg1.p2,seg2.p1-seg2.p2),0.0) && intersectSS(seg1,seg2) ) {
	    mini = 0;
	    goto Skip;
	  } else {
	    Segment seg = nearestSS(seg1,seg2);
	    if( LTE(ans,abs(seg.p1-seg.p2)) ) continue;
	    if( LT(abs(seg.p1-seg.p2),mini) && check(seg,i,j) ) {
	      mini = abs(seg.p1-seg.p2);
	    }
	  }
	}
      }
    Skip:;
      //if( !equals(mini,1e8) ) {
      if( LT(mini,ans) ) {
	G[2+i].push_back((Edge){2+j,mini});
	G[2+j].push_back((Edge){2+i,mini});
      }
    }
  }
  
  if( debug ) {
    rep(i,2+N) {
      puts("");
      if( i < 2 ) cout << "(" << i << ")" << " From : " << ep[i] << endl;
      else        cout << "(" << i << ")" << " From : " << "polygon " << i-2 << " (" << polies[i-2][0] << ")" << endl;
      rep(j,(int)G[i].size()) {
	cout << "  To : " << G[i][j].dst << ", Weight : " << G[i][j].cost << endl;
      }
    } 
  }

  // dijkstra
  ans = min(ans,dijkstra(N+2));
  printf("%.10f\n",ans);
  //printf("%.10f\n",dijkstra(N+2));
  
}

int main(){
  while( cin >> N, N ) {
    rep(i,N) {
      cin >> VN[i] >> Hs[i];
      polies[i].resize(VN[i]);
      rep(j,VN[i]) cin >> polies[i][j].x >> polies[i][j].y;
    }
    double theta, phi;
    cin >> theta >> phi;
    rep(i,2) cin >> ep[i].x >> ep[i].y;
    compute(N,toRad(theta),toRad(phi));
  }
  return 0;
}