POJ 1118 Lining Up:计算几何

UVa 270 / POJ 1118 Lining Up:计算几何2014-07-14 synapse7 270 - Lining Up

Time limit: 3.000 seconds

http://uva.onlinejudge.org/index.php？option=com_onlinejudge&Itemid=8&category=113&page=show_problem&problem=206

http://poj.org/problem？id=1118

``How am I ever going to solve this problem？" said the pilot.

Indeed, the pilot was not facing an easy task. She had to drop packages at specific points scattered in a dangerous area. Furthermore, the pilot could only fly over the area once in a straight line, and she had to fly over as many points as possible. All points were given by means of integer coordinates in a two-dimensional space. The pilot wanted to know the largest number of points from the given set that all lie on one line. Can you write a program that calculates this number？

Your program has to be efficient！

Input

The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.The input consists of N pairs of integers, where 1 < N < 700. Each pair of integers is separated by one blank and ended by a new-line character. The list of pairs is ended with an end-of-file character. No pair will occur twice.

Output

For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line. The output consists of one integer representing the largest number of points that all lie on one line.

Sample Input

11 12 23 39 1010 11

Sample Output

思路：

任取一点，计算出其他点到该点斜率后排序，斜率相同的点必然在一条直线上。复杂度：O（N^2*log N）

UVa的代码：

/*0.129s*/#include<cstdio>#include<cmath>#include<algorithm>using namespace std;const int INF = 1 << 30;char str[20];double x[705], y[705], d[705];int main（void）{int t, n, i, j, k;int ans, count;scanf（"%d
", &t）;///多读一个换行~while （t--）{for （n = 0; gets（str）; ++n）{if （str[0] == ""） break;sscanf（str, "%lf%lf", &x[n], &y[n]）;}//////ans = 1;for （i = 0; i < n - 1; ++i）{for （j = i + 1, k = 0; j < n; ++j, ++k）d[k] = （x[j] == x[i] ？ INF : （y[j] - y[i]） / （x[j] - x[i]））;sort（d, d + k）;count = 1;for （j = 1; j < k; ++j）{if （fabs（d[j] - d[j - 1]） < 1e-9）{++count;ans = max（ans, count）;}else count = 1;}}printf（"%d
", ans + 1）;if （t） putchar（"
"）;}return 0;}

POJ的代码：

/*125ms,204KB*/#include<cstdio>#include<cmath>#include<algorithm>using namespace std;const int INF = 1 << 30;char str[20];double x[705], y[705], d[705];int main（void）{int n, i, j, k;int ans, count;while （scanf（"%d", &n）, n）{for （i = 0; i < n; ++i）scanf（"%lf%lf", &x[i], &y[i]）;ans = 1;for （i = 0; i < n - 1; ++i）{for （j = i + 1, k = 0; j < n; ++j, ++k）d[k] = （x[j] == x[i] ？ INF : （y[j] - y[i]） / （x[j] - x[i]））;sort（d, d + k）;count = 1;for （j = 1; j < k; ++j）{if （fabs（d[j] - d[j - 1]） < 1e-9）{++count;ans = max（ans, count）;}else count = 1;}}printf（"%d
", ans + 1）;}return 0;}