首页 > ACM题库 > HDU-杭电 > hdu 4660 Mathematical Olympiad待解决[解题报告]C++
2015
09-17

hdu 4660 Mathematical Olympiad待解决[解题报告]C++

Mathematical Olympiad

问题描述 :

This is a problem from IMO 2011.

Let S be a finite set of at least two points in the plane. Assume that no three points of S are collinear. A windmill is a process that starts with a line l going through a single point P∈S. The line rotates clockwise about the pivot P until the first time that the line meets some other point belonging to S. This point, Q, takes over as the new pivot, and the line now rotates clockwise about Q, until it next meets a point of S. This process continues indefinitely. Show that we can choose a point P in S and a line l going through P such that the resulting windmill uses each point of as a pivot infinitely many times.

Well… This is not your task. Your task is to determine the expected number of steps we need to run to come back to the original state if we choose the pivot point and the first point we meet at random with equal probability.

输入:

First line, number of test cases, T.
Following are T test cases. For each test case, the first line contains one number, n. Each of the following n lines contains two numbers, X-coordinate and Y-coordinate of one point.

T<=10
3<=n<=1000
Absolute value of all coordinates <= 106
No three points are collinear.

输出:

First line, number of test cases, T.
Following are T test cases. For each test case, the first line contains one number, n. Each of the following n lines contains two numbers, X-coordinate and Y-coordinate of one point.

T<=10
3<=n<=1000
Absolute value of all coordinates <= 106
No three points are collinear.

样例输入:

2
3
0 0
0 1
1 0
4
0 0
0 1
1 0
1 1

样例输出:

3
20/3