BichromeSky
SRM 655 · 2015-03-26 · by cgy4ever
Problem Statement
For the purpose of this problem the sky is a plane and each star is a point in the plane. Note that the constraints enforce that all points are distinct and no three points lie on the same line.
The blue giants are always visible. For each valid i, there is a blue star at (blueX[i], blueY[i]).
The red dwarves are sometimes invisible. For each valid i, there is a red star at (redX[i], redY[i]), but this star is only visible with probability (prob[i]/1000). All of those random choices are mutually independent.
Fox Ciel thinks the sky is beautiful if all blue stars are located inside the convex hull of all visible red stars. Return the probability of this event.
Notes
- The answer will be considered correct if the absolute error or the relative error is at most 1e-9.
Constraints
- redX will contain between 3 and 100 elements, inclusive.
- redX, redY and prob will contain the same number of elements.
- blueX will contain between 3 and 100 elements, inclusive.
- blueX and blueY will contain the same number of elements.
- Each element in redX, redY, blueX and blueY will be between -1,000,000 and 1,000,000, inclusive.
- Each element in prob will be between 1 and 1000, inclusive.
- Among all points (blue and red), no two points will be at the same position, and no three points will be on the same line.
{3,-3,0}
{-1,-1,2}
{400,500,600}
{1,0,-1}
{0,1,0}
Returns: 0.12
There are three blue points and up to three red points in the sky. The convex hull of all red points contains all blue points if and only if all three red points appear. The probability of that event is 0.4 * 0.5 * 0.6 = 0.12.
{3,-3,3,-3}
{3,3,-3,-3}
{200,300,400,500}
{0,1,-1}
{-1,-2,-2}
Returns: 0.088
There are 3 cases in which the convex hull of all red points contains all blue points: {A, B, C, D}, {A, C, D}, {B, C, D}. So both C and D must appear, while at least one of {A, B} must appear. The probability is 0.4 * 0.5 * (1 - (1-0.2)*(1-0.3)) = 0.088.
{3,-3,0}
{-1,-1,2}
{400,500,600}
{1,0,-1,123456}
{0,1,0,-654321}
Returns: 0.0
Even if we get all red points, we can't cover the blue one at (123456,-654321).
{0,-2,-3,-4,-3,-2,0,2,3,4,3,2}
{4,3,2,0,-2,-3,-4,-3,-2,0,2,3}
{501,502,503,504,505,506,507,508,509,510,511,512}
{1,-1,-1,1}
{1,1,-1,-1}
Returns: 0.6555037822772468
{0,1,-3,3}
{0,4,-2,-2}
{200,300,400,500}
{0,-1,1}
{1,-1,-1}
Returns: 0.06
Submissions are judged against all 63 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class BichromeSky with a public method double totallyCovered(vector<int> redX, vector<int> redY, vector<int> prob, vector<int> blueX, vector<int> blueY) · 63 test cases · 2 s / 256 MB per case