H |
You
are around me … Input: Standard Input Output: Standard Output |
A jano shohoj shikarokti ami jugantori noi, A jano bhishon akkhep amar ami digbijoee noi … … Bindu ami tumi amaye
ghire Upobritter bhetor
shudhu tumi achho… |
Its my honest confession that I am not revolutionary And I also regret that I am not a world beater … … I am a point and you
surround me like an ellipse And no one else is
there within |
The above lines are taken from a
super hit romantic song (A bit changed though) of
After listening to this song about a hundred times (Roughly 7.5 hours continuously), a funny geometric thought came to Arif’s mind: if every boy was at the center of an ellipse and if only one girl was placed in it for him, then he (Arif) would not have turned into Casanova. The girls of course cannot go out of the ellipse, the ellipses cannot intersect and the poor boy stuck at the center. Maintaining these constraints the ellipses should be as large as possible, so that the girls can gossip with one another, standing on the edge of their respective ellipses.
You will be given the Cartesian coordinates of at most 15000 boys, and the eccentricity and orientation of the ellipses. You will have to find the maximum possible area of the ellipses. All the ellipses should have same and maximum possible area, same eccentricity and orientation.
Fig
1: Above you can see four ellipses are drawn keeping four men at the center.
In this orientation these ellipses have the maximum possible area. |
Fig 2: This figure shows an ellipse whose length of major
axis is 2a, length of minor axis is 2b, and the major axis makes an angle
theta with the horizon. The eccentricity of the ellipse is . The center of an ellipse is the intersection point of
major axis and minor axis. |
The input file contains maximum 15 test cases. The description of each test case is given below:
First line of each test case contains one integer N (1<N<15001) and two floating-point numbers e (0.2<e≤1) and theta (-90<theta≤90, theta is in degree). Each of the next N lines contains two floating-point numbers which denote the coordinate of a boy.
Input is terminated by a line where the values of N, e and theta are zero.
For each test case produce two lines of outputs. The first line contains the serial of output and the second line contains the maximum possible area of the ellipse. Print six digits after the decimal point. Errors due to precision problems will be ignored.
2
0.400000 10 100
100 200
200 0
0.000000 0 |
Case
1: 15298.744584 |
Problem setter: Shahriar Manzoor, Special Thanks: Derek Kisman