Connection Status:
Competition Arena > TrianglePainting

TrianglePainting

2015 TCO 2A · 2015-04-08 · by lg5293

2015 TCO 2A · 2015-04-08 · by lg5293 · Geometry
Class Name: TrianglePainting
Return Type: double
Method Name: expectedArea
Arg Types: (vector<int>, vector<int>, vector<int>, vector<int>, vector<int>)
Problem Statement

Problem Statement

Cat Noku has a list of N paintbrushes to use for his next masterpiece. The paintbrushes are labeled from 0 to N-1, and are described by the int[]s x1,y1,x2,y2. Each paintbrush is a nondegenerate triangle. The vertices of paintbrush i have coordinates (0,0), (x1[i],y1[i]), (x2[i],y2[i]).

Noku will go through his paintbrushes from 0 to N-1 and he will use the int[] prob to help him paint his masterpiece. Initially his masterpiece is a single point. He repeats the following procedure for each paintbrush.

  • He chooses to use paintbrush i with probability prob[i] / 100.
  • If he chooses to use the paintbrush i, he will place the brush (without rotating it) so that the point (0,0) of the paintbrush will lie somewhere on the boundary of his current masterpiece.
  • He will then make a stroke with the paintbrush. During the stroke, the brush will move (again, without any rotation) around the entire boundary of the current masterpiece in such a way that the point (0,0) of the paintbrush always lies on the boundary of the current masterpiece. The region painted by the stroke is added to the masterpiece.

Compute and return the expected area of Noku's final masterpiece.

Notes

  • Your return value must have an absolute or relative error smaller than or equal to 1e-6.

Constraints

  • N will be between 1 and 2,500, inclusive.
  • x1,y1,x2,y2,prob will each have exactly N elements.
  • Each element of x1,y1,x2,y2 will be between -100 and 100, inclusive.
  • Each triangle will have a positive area.
  • Each element of prob will be between 1 and 100, inclusive.
Examples
0)
{1,-2,-4}
{2,3,-1}
{2,2,-2}
{-1,-1,1}
{100,100,100}
Returns: 52.5

Cat Noku has the following paintbrushes: All the paintbrushes will be used. The final masterpiece will look as follows: Note that in the drawing of the final masterpiece each color represents just the area added to the masterpiece after using the brush of the corresponding color, and not the area actually painted by that brush.

1)
{1,-2,-4}
{2,3,-1}
{2,2,-2}
{-1,-1,1}
{50,50,50}
Returns: 15.0
2)
{1}
{1}
{1}
{-1}
{1}
Returns: 0.01
3)
{1,1,1,1,1,1,1,1,1,1}
{-1,1,-1,1,-1,1,-1,1,-1,1}
{1,1,1,1,1,1,1,1,1,1}
{1,-1,1,-1,1,-1,1,-1,1,-1}
{10,20,30,40,50,60,70,80,90,100}
Returns: 31.899999999999995
4)
{-6,-2,-10,9,8,-1,10,5,7,3}
{-5,2,-5,6,6,-10,8,7,-4,-5}
{5,-1,-1,-8,6,7,10,-6,6,3}
{0,-5,-7,4,10,0,10,-3,-3,-4}
{71,100,43,59,51,41,11,53,3,27}
Returns: 940.1964999999999

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

Coding Area

Language: C++17 · define a public class TrianglePainting with a public method double expectedArea(vector<int> x1, vector<int> y1, vector<int> x2, vector<int> y2, vector<int> prob) · 43 test cases · 2 s / 256 MB per case

Submitting as anonymous