本文主要是介绍POJ 1188 解题报告，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
看discuss和2606一样，稍改一下也交了。区别只是单输入还是多输入。
之前已经做过求最多点在同一条线上的问题了。当时测试数据要比这里复杂很多。比如double的精度，第一个点就是基准点等这里都没有考虑，但还是第一次就过了。
但基本算法是一样的。对所有的点进行遍历，作为基准点，看从这个点出发的直线最多通过多少别的点，加上1即可。基准点确定后，求所有其他点的斜率，按斜率排序，扫描看连续多少个点的斜率一样。
| thestoryofsnow | 2606 | Accepted | 184K | 32MS | C++ | 1475B |
thestoryofsnow | 1118 | Accepted | 192K | 235MS | C++ | 1448B |
/*
ID: thestor1
LANG: C++
TASK: poj1118
*/
#include <iostream>
#include <fstream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <limits>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <cassert>using namespace std;const int MAXN = 700;class Point
{
public:int x, y;double slope;Point() {}Point(int x, int y) : x(x), y(y) {}inline bool operator< (const Point& rhs) const {return this->slope < rhs.slope;}
};double calculateSlope(const Point &p1, const Point &p2)
{if (p2.x == p1.x){return numeric_limits<double>::max(); }return (p2.y - p1.y) * 1.0 / (p2.x - p1.x);
}int main()
{// 1 < N < 700int N;Point points[MAXN];while (scanf("%d", &N) && N){// printf("N = %d\n", N);for (int i = 0; i < N; ++i){scanf("%d%d", &points[i].x, &points[i].y);}int maxp = 0;for (int i = 0; i < N; ++i){for (int j = 0; j < N; ++j){points[j].slope = calculateSlope(points[i], points[j]);}sort(points, points + N);double ps = points[0].slope, p = 1;for (int j = 1; j < N; ++j){if (j == i){continue;}if (points[j].slope == ps){p++;}else{if (p > maxp){maxp = p;}ps = points[j].slope;p = 1; }}}printf("%d\n", maxp + 1);}return 0;
}这篇关于POJ 1188 解题报告的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
