JOIN
Get Time

   Problem Statement  

 Problem Statement for Constellation

Problem Statement

    Fox Ciel has a map of the night sky. On this map she found a constellation that consists of n stars, numbered 0 through n-1 in no particular order.





You are given int[]s x, y, and prob. For each i, star i is located at coordinates (x[i],y[i]) on the map. The probability that star i will be visible when Ciel looks at the sky is prob[i]/1000.





In the evening Ciel is going to take a look at the night sky. She will find the constellation in the sky, and mark all the visible stars on her map. She will then compute the area of the convex hull of the visible stars. Compute and return the expected value of that area.
 

Definition

    
Class:Constellation
Method:expectation
Parameters:int[], int[], int[]
Returns:double
Method signature:double expectation(int[] x, int[] y, int[] prob)
(be sure your method is public)
    
 

Notes

-The events that represent the visibility of individual stars are mutually independent. Thus you may assume that the visibility of each star was independently generated at random with the given probability, just before Ciel looked at the sky.
-Whenever there is a line that contains all the visible stars, the area of their convex hull is 0.
-Return values with absolute or relative error at most 1e-9 will be accepted as correct.
 

Constraints

-x will contain between 3 and 50 elements, inclusive.
-x, y and prob will contain same number of elements.
-Each element in x will be between -100 and 100, inclusive.
-Each element in y will be between -100 and 100, inclusive.
-Each element in prob will be between 1 and 1,000, inclusive.
-There will be no two stars at the same position.
 

Examples

0)
    
{0,0,1}
{0,1,0}
{500,500,500}
Returns: 0.0625
We have 3 points (0,0), (0,1), (1,0), all of them have 50% probability to be visible. We have 0.5^3 probability to see all 3 stars, and the area will be 0.5, in all other cases, the area will be 0. So the expectation is 0.5^4 = 0.0625.
1)
    
{0,1,0,1}
{0,0,1,1}
{1000,1000,400,800}
Returns: 0.6000000000000001
Stars 0 and 1 are always visible, thus there are four possible cases:
  • All four stars are visible with probability 0.4 * 0.8 = 0.32, and in that case the area is 1.
  • With probability (1-0.4)*0.8 = 0.48 star 3 is the only invisible star, and the area is 0.5.
  • With probability 0.4*(1-0.8) = 0.08 star 2 is the only invisible star, and the area is 0.5.
  • Finally, with probability (1-0.4)*(1-0.8) = 0.12 only stars 0 and 1 are visible, and the area is 0.
Thus, the answer is 0.32 * 1 + 0.48 * 0.5 + 0.08 * 0.5 + 0.12 * 0 = 0.6.
2)
    
{-1,-1,-1,0,0,0,1,1,1}
{-1,0,1,-1,0,1,-1,0,1}
{500,500,500,500,500,500,500,500,500}
Returns: 1.9375
3)
    
{0,0,1,2,2}
{0,1,2,1,0}
{1000,500,200,500,1000}
Returns: 1.3
4)
    
{1,5,5,8,2,6,9}
{3,6,4,2,5,7,9}
{100,400,200,1000,400,900,600}
Returns: 12.888936
5)
    
{-100,100,-100,100,-42,57,-34,76,35,-75,-54,10,43}
{-100,-100,100,100,52,-57,-84,63,-43,50,63,10,-44}
{1000,1000,1000,1000,342,747,897,325,678,34,53,6,253}
Returns: 40000.0

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
       Single Round Match 595 Round 1 - Division I, Level Three