LaserShooting
SRM 431 · 2008-12-23 · by Gluk
SRM 431 · 2008-12-23 · by Gluk · Brute Force
Problem Statement
Problem Statement
There is a laser cannon at coordinates (0, 0) on the cartesian plane. There are also several targets on the plane. Each target is a vertical line segment, and the endpoints of the i-th target are at coordinates (x[i], y1[i]) and (x[i], y2[i]). A random angle between -Pi/2 and Pi/2, inclusive, is chosen, and a single shot is fired. The angle -Pi/2 is straight down vertically, 0 is straight to the right horizontally, and Pi/2 is straight up vertically. A shot is a straight ray of infinite length starting from the point (0, 0). A shot hits a target if there is a common point between them. Return the expected number of targets that will be hit by the single shot. Hitting a target doesn't change the direction of the laser shot.
Notes
- A return value with either an absolute or relative error of less than 1.0e-9 is considered correct.
Constraints
- x will contain between 1 and 50 elements, inclusive.
- All elements of x will be distinct.
- x, y1 and y2 will contain the same number of elements.
- Each element of x will be between 1 and 1,000, inclusive.
- Each element of y1 and y2 will be between -1,000 and 1,000, inclusive.
- All targets will have positive lengths.
Examples
0)
{739}
{-281}
{971}
Returns: 0.4085848429662569
1)
{335,229,785,285,358,822,550,272,157,915}
{972,-460,-125,-326,-179,-138,640,795,518,-738}
{531,-32,561,913,990,381,385,-741,-391,-348}
Returns: 3.7811636703394518
2)
{727,217}
{-401,971}
{760,-577}
Returns: 1.233020543509081
3)
{87,558,841,440,232,779}
{-614,-646,-66,-307,-515,397}
{-457,356,-875,69,-661,-98}
Returns: 1.1610111575206146
4)
{236,650,774,274,146,730,762}
{392,-376,-181,980,95,-454,-857}
{383,559,-71,-256,-281,-2,-605}
Returns: 1.8550951609466348
74)
{1}
{-1}
{1}
Returns: 0.5
The only one target will be hit with probability 1/2.
75)
{1,2}
{-1,-2}
{1,2}
Returns: 1.0
Both targets will be hit with probability 1/2.
Submissions are judged against all 82 archived test cases, of which 7 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class LaserShooting with a public method double numberOfHits(vector<int> x, vector<int> y1, vector<int> y2) · 82 test cases · 2 s / 256 MB per case