TwoDiagonals
SRM 727 · 2018-01-10 · by Errichto
Problem Statement
Bearland can be represented as a horizontal plane with N distinct points, denoting positions of N cities. The i-th city has coordinates (x[i], y[i]).
Limak is planning to build two infinitely long roads in Bearland. One should go northwest, and the other should go northeast (both these directions are tilted exactly 45 degrees from the vertical direction). It implies that the two roads are perpendicular to each other, and that they have an intersection point (this point can be a city but not necessarily).
Roads increase the trade significantly. A city will be happy if it lies on at least one of the two roads. Help Limak and find the maximum possible number of happy cities.
Constraints
- N will be between 1 and 1000, inclusive.
- x will contain exactly N elements.
- y will contain exactly N elements.
- Each number in x and in y will be between 0 and 999, inclusive.
- Every two cities will be in different points. (No two cities will coincide.)
{1, 4, 4, 5}
{3, 0, 2, 3}
Returns: 4
There are four cities: (1,3), (4,0), (4,2), (5,3). It's possible to draw two lines in such a way that all cities will be happy:
{0, 1, 2, 3, 4, 5}
{2, 2, 2, 2, 2, 2}
Returns: 2
The new roads can go through at most two cities in this case. One of many optimal placements is:
{2, 2, 3, 3}
{2, 3, 2, 3}
Returns: 4
{10, 0, 15, 9}
{10, 0, 15, 11}
Returns: 4
The two roads should intersect in the point (10, 10).
{273, 100, 999, 789, 105}
{838, 200, 999, 0, 560}
Returns: 2
{500, 503, 501}
{200, 197, 199}
Returns: 3
The positions of cities are collinear and the line going through them is tilted exactly 45 degrees from the vertical direction, so Limak can build a road going through all three cities. The placement of the other road doesn't matter.
{0, 2, 4}
{0, 3, 6}
Returns: 2
The positions of cities are again collinear, but Limak can't make all of them happy. This time the line going through the three points isn't tilted exactly 45 degrees from the vertical direction. The best Limak can do is to build one road going through one of cities, and build the other road to go through one of the remaining two cities.
Submissions are judged against all 51 archived test cases, of which 7 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class TwoDiagonals with a public method int maxPoints(vector<int> x, vector<int> y) · 51 test cases · 2 s / 256 MB per case