TopCoder problem "HittingPerfectTarget" used in SRM 365 (Division II Level Three)



Problem Statement

    A player is going to throw a dart. It is guaranteed that the dart will hit a lattice point (a point whose coordinates are both integers) within a square whose vertices are (-100, -100), (-100, 100), (100, 100), (100, -100). All such lattice points have the same probability of being hit.

In this problem, a point is considered to be within a convex polygon if it lies in the interior of the polygon or on its boundary.  In addition, a convex polygon A is considered to be within a convex polygon B if all the points in A are within polygon B.

You are given two convex polygons, both of which are within the square.  A shot is said to be lucky if the dart hits a point that is within both polygons.  Return the probability that the player's shot will be lucky.

The coordinates of the vertices of the first polygon will be given as two int[]s x1 and y1.  The coordinates of the i-th vertex of the polygon are (x1[i], y1[i]).  The vertices will not be given in any specific order (so they are not necessarily in clockwise or counter-clockwise order), but it will be possible to construct a convex polygon using each vertex exactly once.  The second polygon will be described in an analogous manner using int[]s x2 and y2.
 

Definition

    
Class:HittingPerfectTarget
Method:getProbability
Parameters:int[], int[], int[], int[]
Returns:double
Method signature:double getProbability(int[] x1, int[] y1, int[] x2, int[] y2)
(be sure your method is public)
    
 

Constraints

-x1, x2, y1, and y2 will each contain between 3 and 15 elements, inclusive.
-x1 and y1 will contain the same number of elements.
-x2 and y2 will contain the same number of elements.
-Each element of x1, x2, y1, and y2 will be between -100 and 100, inclusive.
-(x1[i], y1[i]) and (x1[j], y1[j]) will be distinct whenever i and j are distinct, i.e., no two vertices of the first polygon will coincide (have both their x and y coordinates equal).
-(x2[i], y2[i]) and (x2[j], y2[j]) will be distinct whenever i and j are distinct, i.e., no two vertices of the second polygon will coincide (have both their x and y coordinates equal).
-It will be possible to construct a convex polygon using each of the points (x1[i], y1[i]) exactly once as its vertices.
-It will be possible to construct a convex polygon using each of the points (x2[i], y2[i]) exactly once as its vertices.
-No three vertices of the first polygon will lie on a single line.
-No three vertices of the second polygon will lie on a single line.
 

Examples

0)
    
{-100, -100, 100, 100}
{-100, 100, -100, 100}
{-100, -100, 100, 100}
{-100, 100, -100, 100}
Returns: 1.0
Both polygons are just the big square.
1)
    
{-99, -98, 0}
{-99, 99, 0}
{99, 98, 0}
{-99, 99, 0}
Returns: 2.475186257765897E-5
Hitting the origin is the only way to make a lucky shot.
2)
    
{0, 0, 1, 1}
{0, 1, 0, 1}
{-54, -99, -100, -100}
{-54, 99, 100, -100}
Returns: 0.0
These polygons are disjoint so it is impossible for the dart to hit a point that is within both of them.
3)
    
{-1, 1, -30, 30, 0}
{-1, -1, 30, 30, 50}
{-2, 2, -60, 60, 0}
{-2, -2, 60, 60, 100}
Returns: 0.03895943169723522
The first polygon lies within the second one.

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=7575

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10780&pm=7575

Writer:

Xixas

Testers:

PabloGilberto , Yarin , Olexiy , ivan_metelsky

Problem categories:

Brute Force, Geometry, Math, Simple Search, Iteration