RedAndBluePoints
SRM 679 · 2016-01-04 · by ltaravilse
SRM 679 · 2016-01-04 · by ltaravilse · Geometry
Problem Statement
Problem Statement
Fox Ciel likes blue points and hates red points.
There are some blue points and some red points in a two-dimensional plane. Ciel wants to draw a convex polygon. The polygon must not contain any red points. On the other hand, it should contain as many blue points as possible. A point on the boundary of a polygon counts as being contained in the polygon. The polygon is allowed to be degenerated: a point and a single line segment do also count as polygons.
You are given fourint[] s: blueX, blueY, redX and redY.
For each valid i, there is a blue point with coordinates blueX[i] and blueY[i].
The red points are described in the same way by redX and redY.
Return the largest number of blue points a valid polygon may contain.
There are some blue points and some red points in a two-dimensional plane. Ciel wants to draw a convex polygon. The polygon must not contain any red points. On the other hand, it should contain as many blue points as possible. A point on the boundary of a polygon counts as being contained in the polygon. The polygon is allowed to be degenerated: a point and a single line segment do also count as polygons.
You are given four
Return the largest number of blue points a valid polygon may contain.
Constraints
- Both blueX and blueY will contain B elements.
- Both redX and redY will contain R elements.
- Both B and R will be between 1 and 50.
- Each element of blueX, blueY, redX and redY will be between 0 and 1000.
- No two points will be in the same exact position.
- No three points will lie on the same line.
Examples
0)
{0,0,10,10}
{0,10,0,10}
{100}
{120}
Returns: 4
There's a square of blue points, and the only red point is outside the square, so the answer is 4.
1)
{0,0,10,10}
{0,10,0,10}
{3}
{4}
Returns: 3
In this case, we have one red point inside the square so we can't use the four blue points, we're only allowed to use 3 of them, that may be for example (0,10), (10,0) and (10,10) to form a triangle.
2)
{0,0,10,10}
{0,10,0,10}
{3,6}
{2,7}
Returns: 2
3)
{0}
{0}
{1}
{1}
Returns: 1
4)
{5, 6, 6}
{9, 0, 5}
{7}
{6}
Returns: 3
Submissions are judged against all 47 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class RedAndBluePoints with a public method int find(vector<int> blueX, vector<int> blueY, vector<int> redX, vector<int> redY) · 47 test cases · 2 s / 256 MB per case