TrianglesContainOriginEasy
SRM 641 · 2014-08-25 · by Kriii
SRM 641 · 2014-08-25 · by Kriii · Geometry, Simple Search, Iteration
Problem Statement
Problem Statement
We have chosen a finite set of points in the plane.
You are given their coordinates in the int[] s x and y:
for each valid i, there is a point with coordinates (x[i],y[i]).
We are interested in triangles with the following properties:
- Each vertex of the triangle is one of our chosen points.
- The point (0,0) lies inside the triangle.
Constraints
- x and y will contain between 3 and 50 elements, inclusive.
- x and y will contain the same number of elements.
- Each element of x and y will be between -1,000 and 1,000, inclusive.
- No two points will be the same.
- No three points will be collinear.
- No point will be on the origin.
- There will be no two points P and Q such that P, Q, and the origin are collinear.
Examples
0)
{928,991,-307,14,830,681,777,256,775,441,517,56,497,-129,392,108,230,258,820,-271,41,-722,575,694,691,371,734,177,-91,917,256,927,-307,-403,-339,-424,392,706,807,10,899,177,-91,815,895,822,-708,279,992}
{-800,912,646,855,-879,-810,750,-99,-866,710,465,892,-3,195,202,311,542,-121,-878,954,944,958,775,-754,929,983,417,761,607,-707,625,-72,636,782,521,901,916,-821,580,79,-971,477,1000,725,-685,734,922,739,464}
Returns: 0
1)
{665,499,-491,357,861,421,770,-83,-696,-759,-730,-423,720,-577,-302,133,918,245,838,33,-249,834,587,658,612,715,309,819,850,861,469,393,118,-400,-455,413,511,518,866,-913,872,-457,112,225,685,-801,736,-396,-840}
{868,586,491,-145,384,46,344,240,840,665,493,932,-193,997,263,334,843,-137,572,888,352,112,-39,485,20,-174,250,93,47,545,-248,505,674,962,924,-274,19,885,85,914,547,321,165,698,-77,734,68,618,611}
Returns: 0
2)
{423,952,615,-694,-400,7,628,-314,581,448,-356,808,844,-429,828,-791,227,495,513,925,12,-498,-520,-331,643,-982,491,-74,426,756,607,652,786,668,-417,-900,-223,913,607,-61,-694,-206,511,-45,655,989,-172,546,-15}
{0,-612,-97,719,502,594,699,324,-101,681,752,-102,714,302,61,641,886,323,64,-1,876,872,714,851,371,886,747,580,814,808,501,503,-38,657,555,719,295,-359,-12,464,966,300,103,333,534,936,139,584,985}
Returns: 0
3)
{-396,196,-833,-49,-846,-527,-675,-78,-625,-465,-832,-682,-335,-969,-774,-380,-154,-518,-245,-551,-403,-306,-818,-465,-907,-38,-956,-410,-676,-519,-792,-249,-575,-437,-207,-668,-99,-596,-704,-190,-298,-697,-771,-738,196,-756,-351,-446,-482}
{-211,-656,-853,-59,-660,-504,470,147,-703,612,-572,-907,-750,-773,321,13,-288,153,-324,754,703,-264,429,-666,671,-875,148,156,966,86,-613,658,887,-543,375,-224,209,-384,-624,423,-269,409,685,-654,-811,996,-910,360,811}
Returns: 0
4)
{-495,729,-30,920,-584,-228,-175,985,-82,665,673,661,33,844,-372,-511,795,818,173,944,572,-72,633,12,-219,886,-307,816,317,-99,187,204,-657,732,450,567,549,-682,740,-964,619,713,-35,950,669,-383,55,991,-118}
{-640,375,-561,-837,-534,-676,-823,-368,-996,171,-783,-340,15,-269,-243,-456,-618,-723,-702,-751,-343,-99,-100,-81,-587,485,-897,-384,-164,-167,-349,-215,-982,-777,49,-595,-529,-706,-488,-986,-834,-298,-648,362,-521,-935,-557,180,-240}
Returns: 0
37)
{-1,-1,1}
{1,-1,0}
Returns: 1
There is exactly one possible triangle. It does contain the origin.
38)
{-1,-1,1,2}
{1,-1,2,-1}
Returns: 2
There are four possible triangles. Two of them contain the origin. One is the triangle with vertices in (-1,1), (-1,-1), and (2,-1). The other is the triangle with vertices in (-1,-1), (1,2), and (2,-1).
Submissions are judged against all 51 archived test cases, of which 7 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class TrianglesContainOriginEasy with a public method int count(vector<int> x, vector<int> y) · 51 test cases · 2 s / 256 MB per case