Connection Status:
Competition Arena > NCool

NCool

SRM 401 · 2008-05-06 · by griffon

SRM 401 · 2008-05-06 · by griffon · Geometry, Search, Simple Math
Class Name: NCool
Return Type: int
Method Name: nCoolPoints
Arg Types: (vector<int>, vector<int>, int)
Problem Statement

Problem Statement

You are given a convex polygon and you must count the number of N-cool points. A point is N-cool if it is a lattice point covered by the polygon and also an endpoint of some N-cool segment. A line segment is N-cool if it contains at least N lattice points that are covered by the polygon. A point is considered covered by the polygon if it is inside or on the boundary of the polygon. Endpoints of a segment are considered to be inside of it. A lattice point is a point with integer coordinates.

Consider the example in the picture below. Here N is equal to 6, and there are 21 6-cool points, marked green. Also two 6-cool segments, which are colored red, are shown.

You are given int[]s x and y describing the vertices of the polygon (in no particular order). The coordinates of each vertex are specified by corresponding elements of x and y. Return the number of N-cool points.

Notes

  • A polygon is convex if it contains all the line segments connecting any pair of its points.

Constraints

  • x and y will each contain between 3 and 50 elements, inclusive.
  • x and y will contain the same number of elements.
  • All elements of x and y will be between 0 and 10000, inclusive.
  • The number of lattice points inside or on the boundary of the specified polygon will not be greater than 500000.
  • N will be between 2 and 500000, inclusive.
  • The polygon specified by x and y will be convex and will have nonzero area.
Examples
0)
{0, 1, 2, 7, 7}
{3, 1, 6, 1, 5}
6
Returns: 21

This is the example from the problem statement.

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

These three points form a triangle, whose sides are 2-cool segments, so all three vertices are 2-cool.

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

One point can be mentioned in the input two or more times.

3)
{0, 1, 1, 2, 2, 3, 3, 4, 4, 5}
{1, 0, 2, 0, 2, 0, 2, 0, 2, 1}
5
Returns: 4

There can be 3 points of the polygon, lying on the same line.

4)
{0, 1, 1, 2, 2, 3, 3, 4, 4, 5}
{1, 0, 2, 0, 2, 0, 2, 0, 2, 1}
4
Returns: 10

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

Coding Area

Language: C++17 · define a public class NCool with a public method int nCoolPoints(vector<int> x, vector<int> y, int n) · 52 test cases · 2 s / 256 MB per case

Submitting as anonymous