TopCoder SRM 595 - 900: Constellation

Problem Statement

给N个二维平面上的点，第i个点有p[i]的概率出现在最终结果中。
问最后存在于最终结果的点所构成的凸包的面积期望是多少。
保证 N <= 50，0.001 <= p[i] <= 1。

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 vector<int> , vector<int> , vector<int>
Returns double
Method signature double expectation(vector<int> x, vector<int> y, vector<int> prob)

(be sure your method is public)

Limits

Time limit (s) 2.000
Memory limit (MB) 64

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.

Test cases

input
- x { 0, 0, 1 }
- y { 0, 1, 0 }
- prob { 500, 500, 500 }
output
Returns 0.0625

note

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.
input
- x { 0, 1, 0, 1 }
- y { 0, 0, 1, 1 }
- prob { 1000, 1000, 400, 800 }
output
Returns 0.6000000000000001
note
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.
input
- x { -1, -1, -1, 0, 0, 0, 1, 1, 1 }
- y { -1, 0, 1, -1, 0, 1, -1, 0, 1 }
- prob { 500, 500, 500, 500, 500, 500, 500, 500, 500 }
output
Returns 1.9375
input
- x { 0, 0, 1, 2, 2 }
- y { 0, 1, 2, 1, 0 }
- prob { 1000, 500, 200, 500, 1000 }
output
Returns 1.3
input
- x { 1, 5, 5, 8, 2, 6, 9 }
- y { 3, 6, 4, 2, 5, 7, 9 }
- prob { 100, 400, 200, 1000, 400, 900, 600 }
output
Returns 12.888936
input
- x { -100, 100, -100, 100, -42, 57, -34, 76, 35, -75, -54, 10, 43 }
- y { -100, -100, 100, 100, 52, -57, -84, 63, -43, 50, 63, 10, -44 }
- prob { 1000, 1000, 1000, 1000, 342, 747, 897, 325, 678, 34, 53, 6, 253 }
output
Returns 40000.0

back to the menu