HittingPerfectTarget
SRM 365 · 2007-09-12 · by Xixas
SRM 365 · 2007-09-12 · by Xixas · Brute Force, Geometry, Math, Simple Search, Iteration
Problem Statement
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 twoint[] 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 usingint[] s x2 and y2.
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.
4)
{-1, 1, -30, 30, 0}
{-1, -1, 30, 30, 50}
{-2, 2, -60, 60, 0}
{-2, -2, 40, 40, 41}
Returns: 0.03551892279894062
Submissions are judged against all 82 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class HittingPerfectTarget with a public method double getProbability(vector<int> x1, vector<int> y1, vector<int> x2, vector<int> y2) · 82 test cases · 2 s / 256 MB per case