首页 > ACM题库 > HDU-杭电 > HDU 1432 Lining Up-计算几何[解题报告] C++
2013
12-10

HDU 1432 Lining Up-计算几何[解题报告] C++

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;
}

解题报告转自:http://blog.csdn.net/hearthougan/article/details/17141297


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