2013
12-10

# Lining Up

“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!

The input consists of multiple test cases, and each case begins with a single positive integer on a line by itself indicating the number of points, followed by N pairs of integers, where 1 < N < 700. Each pair of integers is separated by one blank and ended by a new-line character. No pair will occur twice in one test case.

For each test case, the output consists of one integer representing the largest number of points that all lie on one line, one line per case.

5
1 1
2 2
3 3
9 10
10 11

3

#include <iostream>
#include <cstdio>

using namespace std;

const int MAXN = 750;

int main()
{
int n;
int i, j, k;
int x[MAXN], y[MAXN];

while (cin>>n && n)
{
for (i=0; i<n; i++)
cin>>x[i]>>y[i];
int sum = 0;
for (i=0; i<n; i++)
{
for (j=i+1; j<n; j++)
{
int num = 0;
for (k=j+1; k<n; k++)
if ((x[j] - x[i]) * (y[k] - y[i]) - (y[j] - y[i]) * (x[k] - x[i]) == 0)
num++;
sum = sum > num ? sum : num;
}
}
cout<<sum+2<<endl;
}
return 0;
}

1. 可以参考算法导论中的时间戳。就是结束访问时间，最后结束的顶点肯定是入度为0的顶点，因为DFS要回溯