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 <vector>
#include <array>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <tuple>
#include <bitset>
#include <memory>
#include <cmath>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <numeric>
#include <climits>
#include <cfloat>
#include <cassert>
struct Point {
	double x, y;
	double distance_from(const Point& that) const;
	Point move(const struct Vector& vec) const;
};
struct Vector {
	double dx, dy;
	Vector(const Point& to, const Point& from) : dx{ to.x - from.x }, dy{ to.y - from.y }{};
	Vector(const double _dx, const double _dy) :dx{ _dx }, dy{ _dy }{};
	Vector rotate(const struct Angle& angle) const;
	double dot(const Vector& that) const;
	double cross(const Vector& that) const;
	double length() const;
};
Vector operator-(const Point& to, const Point& from);
Point operator+(const Point& point, const Vector& vec);
Point operator+(const Vector& vec, const Point& point);
struct Line {
private:
	Line(const double _a, const double _b, const double _c) :a{ _a }, b{ _b }, c{ _c }{};
public:
	double a, b, c;
	Line(const Point& p1, const Point& p2) : a{ p2.y - p1.y }, b{ p1.x - p2.x }, c{ p2.x * p1.y - p2.y * p1.x }{};
	Line(const Point& point, const Vector& vec) : Line(point, Point{ point.x + vec.dx, point.y + vec.dy }){};
	double distance_from(const Point& that) const;
	Line shift_vertical(const double dx) const;
	bool is_cross(const Line& that) const;
	Point crosspoint(const Line& that) const;
};
struct Angle {
	double sin, cos;
	static Angle from_sin(const double sin);
	static Angle from_degree(const double degree);
	Angle operator+(const Angle& that) const;
	Angle operator-(const Angle& that) const;
	Angle operator-() const;
	double tangent() const;
};
struct Circle {
	Point center;
	double radius;
	bool contains(const Point& point) const;
};
struct Edge {
	Point from, to;
	double distance_from(const Point& point) const;
	double distance_from(const Edge& that) const;
	bool is_cross(const Edge& that) const;
	Point crosspoint(const Edge& that) const;
};
struct Triangle {
	Point a, b, c;
	std::vector<Edge> edges() const;
	bool contains(const Point& point) const;
	double distance_from(const Point& point) const;
};
struct Convex {
	std::vector<Edge> edges;
	Convex(const std::vector<Point>& vertex);//counter clock wise
	Convex(const std::vector<Edge>& _edges) : edges(_edges) {};//couter clock wise;
	bool has_intersection(const Convex& that) const;
	bool contains(const Point& that) const;
	double min_distance(const Point& point) const;
	double min_distance(const Convex& that) const;
};
Convex make_shadows(const Angle &sun, const Angle sun_height, const std::vector<Point>& vertex, const int height) {
	constexpr double EPS = 1e-9;
	const Vector sun_vec{ sun.cos, sun.sin };
	const Vector shadow_vec{ -sun.cos * height / sun_height.tangent(), -sun.sin * height / sun_height.tangent() };
	const int n = vertex.size();
	std::vector<Point> new_vertex; new_vertex.reserve(vertex.size() + 2);
	int i = 0;
	for (; (vertex[(i + 1) % n] - vertex[i % n]).cross(sun_vec) <= EPS; ++i);
	for (; (vertex[(i + 1) % n] - vertex[i % n]).cross(sun_vec) >= -EPS; ++i);
	for (; (vertex[(i + 1) % n] - vertex[i % n]).cross(sun_vec) < -EPS; ++i) {
		new_vertex.push_back(vertex[i % n]);
	}
	new_vertex.push_back(vertex[i % n]);
	for (; std::abs((vertex[(i + 1) % n] - vertex[i % n]).cross(sun_vec)) < EPS; ++i);
	for (; (vertex[(i + 1) % n] - vertex[i % n]).cross(sun_vec) > EPS; ++i) {
		new_vertex.push_back(vertex[i % n] + shadow_vec);
	}
	new_vertex.push_back(vertex[i % n] + shadow_vec);
	return Convex(new_vertex);
}
int main() {
	auto comparator = [](const std::pair<int, double>& a, const std::pair<int, double>& b) {return a.second > b.second; };
	while (true) {
		int n; std::cin >> n; if (n == 0) break;
		std::vector<std::pair<int, std::vector<Point>>> building(n);
		for (auto i = 0; i < n; ++i) {
			int nv, height; std::cin >> nv >> height;
			std::vector<Point> point(nv);
			for (auto& p : point) std::cin >> p.x >> p.y;
			building[i] = std::make_pair(height, std::move(point));
		}
		int sun_dir, sun_height; std::cin >> sun_dir >> sun_height;
		auto sun_dir_angle = Angle::from_degree(sun_dir);
		auto sun_height_angle = Angle::from_degree(sun_height);
		Point start, goal; std::cin >> start.x >> start.y >> goal.x >> goal.y;
		std::vector<Convex> shadows; shadows.reserve(n);
		std::transform(building.begin(), building.end(), std::back_inserter(shadows), [sun_dir_angle, sun_height_angle](const std::pair<int, std::vector<Point>>& p) {return make_shadows(sun_dir_angle, sun_height_angle, p.second, p.first); });
		std::vector<std::vector<double>> min_distance(n + 2, std::vector<double>(n + 2, 0.0));
		min_distance[n][n + 1] = min_distance[n + 1][n] = start.distance_from(goal);
		for (auto i = 0; i < n; ++i) {
			min_distance[i][n] = min_distance[n][i] = shadows[i].min_distance(start);
			min_distance[i][n + 1] = min_distance[n + 1][i] = shadows[i].min_distance(goal);
			for (auto j = 0; j < i; ++j) {
				min_distance[i][j] = min_distance[j][i] = shadows[i].min_distance(shadows[j]);
			}
		}
		std::priority_queue<std::pair<int, double>, std::vector<std::pair<int, double>>, decltype(comparator)> queue(comparator); queue.emplace(n, 0);
		std::vector<double> min_walk(n + 2, DBL_MAX); min_walk[n] = 0;
		while (!queue.empty()) {
			auto top = queue.top(); queue.pop();
			if (min_walk[top.first] == top.second) {
				for (auto i = 0; i < min_walk.size(); ++i) {
					if (min_walk[i] > min_distance[top.first][i] + top.second) {
						min_walk[i] = min_distance[top.first][i] + top.second;
						queue.emplace(i, min_walk[i]);
					}
				}
			}
		}
		std::cout << std::setprecision(10) << std::fixed << min_walk[n + 1] << '\n';
	}
}


double Line::distance_from(const Point& that) const
{
	return std::abs(a * that.x + b * that.y + c) / std::sqrt(a * a + b * b);
}

Line Line::shift_vertical(const double length) const
{
	const auto len = std::sqrt(a * a + b * b);
	const auto dx = -a / len * length;
	const auto dy = b / len * length;
	return Line(a, b, c + b * dy - a * dx);
}

bool Line::is_cross(const Line& that) const
{
	return std::abs(a * that.b - b * that.a) >= 1e-9;
}

Point Line::crosspoint(const Line& that) const
{
	assert(is_cross(that));
	const auto d = a * that.b - b * that.a;
	return Point{ (b * that.c - c * that.b) / d, (c * that.a - a * that.c) / d };
}

double Point::distance_from(const Point& that) const
{
	return Vector(*this, that).length();
}

Point Point::move(const Vector& vec) const
{
	return Point{ x + vec.dx, y + vec.dy };
}

Vector Vector::rotate(const Angle& angle) const
{
	return Vector{dx * angle.cos - dy * angle.sin, dx * angle.sin + dy * angle.cos};
}

double Vector::dot(const Vector& that) const
{
	return dx * that.dx + dy * that.dy;
}

double Vector::cross(const Vector& that) const
{
	return dx * that.dy - dy * that.dx;
}

double Vector::length() const
{
	return std::sqrt(dx * dx + dy * dy);
}

Angle Angle::from_sin(const double sin)
{
	return Angle{ sin, std::sqrt(1 - sin * sin) };
}

Angle Angle::from_degree(const double degree)
{
	const auto rad = std::acos(-1) * degree / 180;
	return Angle{std::sin(rad), std::cos(rad)};
}

Angle Angle::operator+(const Angle& that) const
{
	return Angle{ sin * that.cos + cos * that.sin, cos * that.cos - sin * that.sin };
}

Angle Angle::operator-(const Angle& that) const
{
	return Angle{ sin * that.cos - cos * that.sin, cos * that.cos + sin * that.sin };
}

Angle Angle::operator-() const
{
	return Angle{ -sin, cos };
}

double Angle::tangent() const
{
	return sin / cos;
}

std::vector<Edge> Triangle::edges() const
{
	std::vector<Edge> result{Edge{ a, b }, Edge{ b, c }, Edge{ c, a }};
	return result;
}

bool Triangle::contains(const Point& point) const
{
	auto ab = Vector(a, b).cross(Vector(point, b));
	auto bc = Vector(b, c).cross(Vector(point, c));
	auto ca = Vector(c, a).cross(Vector(point, a));
	return (ab >= 0 && bc >= 0 && ca >= 0) || (ab <= 0 && bc <= 0 && ca <= 0);
}

double Triangle::distance_from(const Point& point) const
{
	const auto edge = edges();
	double min_distance = DBL_MAX;
	for (const auto& e : edge) min_distance = std::min(min_distance, e.distance_from(point));
	return min_distance;
}

double Edge::distance_from(const Point& point) const
{
	Vector vec(to, from);
	if (vec.dot(Vector(point, from)) >= 0 && vec.dot(Vector(point, to)) <= 0) return Line(from, to).distance_from(point);
	else return std::min(to.distance_from(point), from.distance_from(point));
}

double Edge::distance_from(const Edge& that) const
{
	if (is_cross(that)) return 0.0;
	return std::min({distance_from(that.to), distance_from(that.from), that.distance_from(to), that.distance_from(from)});
}

bool Edge::is_cross(const Edge& that) const
{
	Vector vec(to, from);
	Vector that_vec(that.to, that.from);
	if (vec.cross(that_vec) == 0) return std::abs(vec.cross(that.to - from)) < 1e-9 && std::min(from.x, to.x) <= std::max(that.from.x, that.to.x) && std::min(that.from.x, that.to.x) <= std::max(from.x, to.x) && std::min(from.y, to.y) <= std::max(that.from.y, that.to.y) && std::min(that.from.y, that.to.y) <= std::max(from.y, to.y);
	return vec.cross(that.to - from) * vec.cross(that.from - from) <= 0 && that_vec.cross(to - that.from) * that_vec.cross(from - that.from) <= 0;
}

Point Edge::crosspoint(const Edge& that) const
{
	assert(is_cross(that));
	return Line(to, from).crosspoint(Line(that.to, that.to));
}

bool Circle::contains(const Point& point) const
{
	return center.distance_from(point) <= radius;
}


Vector operator-(const Point& to, const Point& from)
{
	return Vector{ to.x - from.x, to.y - from.y };
}

Point operator+(const Point& point, const Vector& vec)
{
	return Point{ point.x + vec.dx, point.y + vec.dy };
}

Point operator+(const Vector& vec, const Point& point)
{
	return Point{ point.x + vec.dx, point.y + vec.dy };
}

Convex::Convex(const std::vector<Point>& vertex)
{
	edges.reserve(vertex.size());
	for (auto i = 0; i < vertex.size(); ++i) {
		edges.push_back(Edge{ vertex[i], vertex[(i + 1) % vertex.size()] });
	}
}

bool Convex::has_intersection(const Convex& that) const
{
	if (contains(that.edges.front().from) || that.contains(edges.front().from)) return true;
	for (const auto& a : edges) for (const auto& b : that.edges) if (a.is_cross(b)) return true;
	return false;
}

bool Convex::contains(const Point& that) const
{
	for (const auto& e : edges) if ((e.to - e.from).cross(that - e.from) < 0) return false;
	return true;
}

double Convex::min_distance(const Point& point) const
{
	if (contains(point)) return 0.0;
	double min = DBL_MAX;
	for (const auto& e : edges) min = std::min(min, e.distance_from(point));
	return min;
}

double Convex::min_distance(const Convex& that) const
{
	if (has_intersection(that)) return 0.0;
	double min = DBL_MAX;
	for (const auto& a : edges) for (const auto& b : that.edges) min = std::min(min, a.distance_from(b));
	return min;
}