LineDraw

SRM 97 · 2002-06-12 · by brett1479

Class Name: LineDraw

Return Type: int

Method Name: numPoints

Arg Types: (vector<int>, vector<int>)

Problem Statement

Given a plane containing points you are going to play connect the points. You will draw 2 separate straight lines. The lines may cross. Return how many points are not hit by either of your lines. You must pick the lines so that the return value is minimized. Note, a line extends infinitely in either direction. See examples for further clarification.

Create a class LineDraw that contains the method numPoints, which takes a int[] xs and an int[] ys representing the points in the plane, and returns an int that is the minimal amount of points not hit by either of your lines.

Notes

Point K will have x-coordinate xs[K] and y-coordinate ys[K].

Constraints

xs and ys will contain the same number of elements.
xs and ys will contain between 0 and 25 elements, inclusive.
The elements of xs will be between -20000 and 20000, inclusive.
The elements of ys will be between -20000 and 20000, inclusive.
There will be no repeated points.

Examples

{0,0,0,1,1,1,2,2,2}
{0,1,2,0,1,2,0,1,2}
Returns: 3

{0,0,0}
{1,2,3}
Returns: 0

{1,2,3}
{0,0,0}
Returns: 0

{0,1,1,2,2}
{0,0,1,0,2}
Returns: 0

{-1000,0,1000,-1000,0,1000,-1000,0,1000}
{1000,1000,1000,0,0,0,-1000,-1000,-1000}
Returns: 3

61)

{0,0,0,2,2,2,4,4,4}
{0,2,4,0,2,4,0,2,4}
Returns: 3

This would look like ('.'s represent points, 'X's represent the axes): . . . X . . . X XXXXXX.X.X.XXX X X X X Two lines must be drawn so that the least number of points are not on either line. Here is one possible pair of lines that satisfy the requirement: -------------- X -------------- X XXXXXX.X.X.XXX X X X X There are other possible pairs of lines that produce the same result. There are 3 points through which lines do not pass so your method returns 3.

62)

{-2,0,0,2,2}
{0,0,2,0,4}
Returns: 0

This would look like: X . X . X XXXX.X.X.XXXXX X X X X Two lines must be drawn so that the least number of points are not on either line. This would look like: X / X/ / /X -------------- / X / X / X / X There are 0 points through which lines do not pass so your method returns 0.

Submissions are judged against all 69 archived test cases, of which 7 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class LineDraw with a public method int numPoints(vector<int> xs, vector<int> ys) · 69 test cases · 2 s / 256 MB per case