BichromeSky2
SRM 675 · 2015-11-03 · by cgy4ever
Problem Statement
You are going to take a photo of the night sky. The photo will be a two-dimensional plane. For each i, star i will be a point located at the coordinates (x[i], y[i]).
Once you have the photo, you are going to draw two convex polygons: the convex hull of all red stars, and the convex hull of all blue stars. Note that these may sometimes be degenerate. It is even possible that all stars will have the same color, in which case the other convex hull is empty. Finally, you are going to compute the area of the intersection of those two polygons.
You are given the
Notes
- Your return value must have a relative or absolute error less than 1e-9
Constraints
- x will contain between 6 and 50 elements, inclusive.
- x, y and prob will contain the same number of elements.
- Each element in x will be between -1,000 and 1,000, inclusive.
- Each element in y will be between -1,000 and 1,000, inclusive.
- Each element in prob will be between 0 and 1,000, inclusive.
- All points will be distinct.
- No three points will lie on the same line.
{0,0,3,1,-2,1}
{0,3,0,1,1,-2}
{0,0,0,1000,1000,1000}
Returns: 1.0000000000000004
Stars 0, 1, and 2 are guaranteed to be blue. Stars 3, 4, and 5 are guaranteed to be red. The two convex hulls are uniquely determined. Their intersection is the square bounded by the lines x=0, x=1, y=0, and y=1. The area of this square is 1.
{0,0,3,1,-2,1}
{0,3,0,1,1,-2}
{0,0,0,200,300,400}
Returns: 0.02400000000000005
In this example, stars 3, 4, and 5 are sometimes red and sometimes blue. If there are fewer than three red stars, the convex hull of all red stars will have no area, and therefore the area of the intersection will be 0. Thus, an intersection with a non-empty area only exists if all three of these stars are red. That happens with probability (200/1000) * (300/1000) * (400/1000) = 0.024. In that case the area of the intersection is 1. (This is the case shown in Example 0). Thus, the expected area of the intersection is 0.024 * 1 = 0.024.
{0,0,3,1,-2,1}
{0,3,0,1,1,-2}
{500,500,500,500,500,500}
Returns: 0.06250000000000008
{-1,-3,-2,-3,1,2,1,0}
{3,1,-3,-1,3,0,-3,-1}
{249,752,863,67,97,348,526,711}
Returns: 2.4451606306816163
{302,890,-174,311,-84,903,-639,-793,-59,-766,-909,671,826,-117,-989,-616,-170,922,895,71,209,-551,-923,498,909,
851,636,-120,374,-207,-320,88,-668,-451,-117,-842,-370,824,674,-763,7,163,-229,-525,366,-358,706,1000,-547,403}
{-532,606,848,197,-378,-66,512,-189,226,125,-924,851,-837,-315,41,-828,-743,695,864,-504,671,731,256,-48,432,378,
813,130,-298,752,-482,497,57,826,612,-855,-347,232,-909,487,-456,59,846,112,-471,816,687,657,542,115}
{453,921,58,99,461,444,722,972,763,981,18,557,919,153,330,708,254,910,370,686,407,528,668,205,777,184,156,175,553,
292,984,317,580,665,114,378,705,59,17,928,552,414,801,466,575,341,161,673,119,302}
Returns: 2463608.2458090265
Submissions are judged against all 45 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class BichromeSky2 with a public method double expectationOfArea(vector<int> x, vector<int> y, vector<int> prob) · 45 test cases · 2 s / 256 MB per case