朴素做法是 O(n
3) 的,超时。我的做法是枚举每个点,然后求其它点和它连线的斜率,再排序。这样就得到经过该点的直线最多能经过几个点。求个最大值就行了。复杂度是 O(n
2logn) 的。把排序换成 hash,可以优化到 O(n
2)。
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
/**//*************************************************************************
Author: WHU_GCC
Created Time: 2007-8-21 18:58:04
File Name: pku1118.cpp
Description:
************************************************************************/
#include <iostream>
#include <cmath>
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#define out(x) (cout << #x << ": " << x << endl)
typedef long long int64;
const int maxint = 0x7FFFFFFF;
const int64 maxint64 = 0x7FFFFFFFFFFFFFFFLL;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
template <class T> void show(T a, int n)
{ for (int i = 0; i < n; ++i) cout << a[i] << ' '; cout << endl; }
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
template <class T> void show(T a, int r, int l)
{ for (int i = 0; i < r; ++i) show(a[i], l); cout << endl; }
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
const int maxn = 1000;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
typedef struct point_t
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int x, y;
};
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
bool d_equal(const double &a, const double &b)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
return abs(a - b) < 1e-9;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
point_t p[maxn];
int n;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
double slope[maxn];
int m;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
while (scanf("%d", &n), n != 0)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
for (int i = 0; i < n; i++)
scanf("%d%d", &p[i].x, &p[i].y);
int ans = 0;
for (int i = 0; i < n; i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
m = 0;
for (int j = 0; j < n; j++) if (i != j)
slope[m++] = double(p[j].y - p[i].y) / (p[j].x - p[i].x);
sort(slope, slope + m);
int cnt = 1;
for (int j = 1; j < m; j++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if (d_equal(slope[j], slope[j - 1]))
cnt++;
else
cnt = 1;
ans >?= cnt;
}
}
printf("%d\n", ans + 1);
}
return 0;
}