시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
10 초 (추가 시간 없음) | 512 MB | 13 | 8 | 7 | 58.333% |
Consider a set of points P in the plane such that no 3 points are collinear. Construct a windmill as follows:
During this process, a given point in P can be a pivot multiple times. Considering all possible starting pivots and orientations, find the maximum number of times that a single point can be promoted during a single 360° rotation of a windmill. Note that the first point is a pivot, but not promoted to be a pivot at the start.
The first line of input contains a single integer n (2 ≤ n ≤ 2000), which is the number of points p ∈ P.
Each of the next n lines contains two space-separated integers x and y (−105 ≤ x, y ≤ 105). These are the points. Each point will be unique, and no three points will be collinear.
Output a single integer, which is the maximum number of times any point p ∈ P can be promoted, considering a full 360° rotation and any arbitrary starting point.
3 -1 0 1 0 0 2
2
6 0 0 5 0 0 5 5 5 1 2 4 2
3