Visibility Measure
문제 정보

 문제 ID
 시간 제한
 메모리 제한
 제출 횟수
 정답 횟수 (비율)

 VISIBILITY
 1000ms
 65536kb
 8
 3 (37%)

 출처
 분류
문제
In computer graphics, identifying visible lines and surfaces is an important task.
When a polygon or a polyhedron is rendered by a graphical program, only visible parts(lines and surfaces) are considered and rendered.
This might reduce the computational time and space, and most of all, it makes the rendered object to be realistic.
![judgeattachments/6ba8d6588d3d6102525e45582928851f/figure1.png](http://algospot.com/media/judgeattachments/6ba8d6588d3d6102525e45582928851f/figure1.png)
Consider a polyhedron(pentahedron) in the figure.
When it is viewed from the front, only two surfaces are visible and rendered as in the figure in the middle.
However, if the other surfaces are rendered as in the rightmost figure,
the result is not realistic(it is rather like bottomback view).
When a polygon on two dimensional plane is given, the visibility measure could be defined roughly as follows.
If there exists a point outside the polygon where the number of visible line segments of the polygon is K, we say that the polygon is Kvisible.
The visibility measure of the polygon is the maximum value of K.
A formal definition is as follows:
First, let S be the set of points on the boundary of a polygon.
For a point , a point is visible from q if and only if
where denotes the distance between q and r.
For a fixed q, we define V(q,S) as the set of line segments of polygon S which are visible from q.
If there exists a point where the cardinality(number of elements) of V(q',S) is K, we say that S is Kvisible.
The visibility measure of S is the maximum value of K which satisfies that S is Kvisible.
Given a convex polygon S on two dimensional plane, write a program to compute the visibility measure of S.
입력
Your program is to read from standard input. The input consists of T test cases.
The number of test cases T is given in the first line of the input.
The first line of each test case contains an integer, n(3 <= n <= 20,000),
the number of vertices of S.
Each line of the next n lines contains two integers, x and y,
where (x, y) is the coordinates of each vertex (10^9 <= x,y <= 10^9).
For each test case, the order of vertices would be either clockwise or counterclockwise, and no three points(vertices) are colinear.
출력
Your program is to write to standard output. Print exactly one line for each test case.
The line should contain an integer indicating the visibility measure of the given polygon.
예제 입력
2 4 2 1 2 1 2 1 2 1 7 0 0 127 0 205 69 180 153 97 169 13 152 68 76
예제 출력
2 3
노트