Connection Status:
Competition Arena > Constellation

Constellation

SRM 595 · 2013-06-25 · by cgy4ever

SRM 595 · 2013-06-25 · by cgy4ever · Geometry
Class Name: Constellation
Return Type: double
Method Name: expectation
Arg Types: (vector<int>, vector<int>, vector<int>)
Problem Statement

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.

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

Submissions are judged against all 87 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class Constellation with a public method double expectation(vector<int> x, vector<int> y, vector<int> prob) · 87 test cases · 2 s / 256 MB per case

Submitting as anonymous