407925: GYM102944 B Bois Blanc

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

B. Bois Blanctime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

Bois Blanc is the French name for a special type of basswood. But if you are an expert on Michigan geography, you know that it is also a Michigan island at the northern end of Lake Huron. Of course, there are lots of basswood trees on the island. Unlike its famous and historical neighboring island – Mackinac Island – there are very few residents and visitors on Bois Blanc Island. It is known primarily for its lighthouses, which help guide ships entering and leaving the Mackinac Straits connecting Lake Huron and Lake Michigan.

Let us suppose that Bois Blanc is perfectly circular (it's not, but it's difficult to come up with a problem for the real Bois Blanc shape). Designate a Cartesian coordinate system where the origin $$$(0,0)$$$ is at the center of the island and the island has radius 1. The State of Michigan has decided to build $$$N$$$ state-of-the-art lighthouses on the island, numbered $$$1,2,\ldots , N$$$. Lighthouse $$$i$$$ will be located at $$$(x_i, y_i)$$$ and have a specific light angle $$$\alpha_i$$$ and an angle of vision $$$\theta_i$$$ (see figure). Thus, the lighthouse illuminates the area between two rays, the first extending from $$$(x_i,y_i)$$$ at angle $$$\alpha_i-\theta_i/2$$$ and the second extending from $$$(x_i,y_i)$$$ at angle $$$\alpha_i+\theta_i/2$$$.

You have just been appointed Michigan Lighthouse Commissioner (congratulations!). You would like to ensure that these lighthouses altogether light up the entire periphery of the island (if all the lights are on) so that ships do not run ashore on the island. Island periphery is the circumference of the island. You are tasked to write a program that certifies this for you.

Input

The first line in each input file contains an integer $$$N$$$ ($$$1\le N\le 100$$$), indicating the number of lighthouses on the island. In each of the next $$$N$$$ lines, there are four real numbers $$$x_i, y_i, \alpha_i, \theta_i$$$ ($$$x_i^2+y_i^2 < 1$$$; $$$0\le \alpha_i < 2\pi$$$; $$$0 < \theta_i < \pi$$$). Angles are given in radians.

The input is guaranteed that if you move the coordinates and angles of a lighthouse by $$$\pm 10^{-4}$$$, the answer will not change.

Output

For each test case, output YES if all lighthouses altogether light up the periphery of the island, and output NO otherwise.

ExamplesInput
4
0.2 0.2 0.785398 1.570796
-0.2 0.2 2.356194 1.570796
-0.2 -0.2 3.926990 1.570796
0.2 -0.2 5.497787 1.570796
Output
NO
Input
4
0.3 -0.2 0.785398 1.570796
0.2 0.3 2.356194 1.570796
-0.3 0.2 3.926990 1.570796
-0.2 -0.3 5.497787 1.570796
Output
NO
Input
4
0.2 -0.3 0.785398 1.570796
0.3 0.2 2.356194 1.570796
-0.2 0.3 3.926990 1.570796
-0.3 -0.2 5.497787 1.570796
Output
YES
Input
8
0.160778 -0.455910 2.270371 2.260020
-0.059877 -0.152423 2.615438 2.349560
0.092217 -0.908759 3.937581 2.103347
0.634763 0.439841 0.246451 0.232265
-0.291208 0.939505 6.245182 2.622931
0.005957 0.114427 1.133582 1.039842
-0.303909 0.652162 4.819728 0.999183
-0.625112 -0.292457 5.316244 0.593612
Output
YES

加入题单

上一题 下一题 算法标签: