poj 1118
#include<iostream>
using namespace std;
#define N 700
struct point {int x,y;} pnt[N];
int main()
{
int n,i,j,k,max,cnt;
while(scanf("%d",&n)&&n)
{
for(i=;i<n;i++)
scanf("%d%d",&pnt[i].x,&pnt[i].y);
max=;
for(i=;i<n;i++)
for(j=i+;j<n;j++)
{
cnt=;
for(k=j+;k<n;k++)
{
if(k==i||k==j) continue;
int left=(pnt[i].x-pnt[k].x)*(pnt[j].y-pnt[k].y);
int right=(pnt[j].x-pnt[k].x)*(pnt[i].y-pnt[k].y);
if(left==right) cnt++;
}
max=max>cnt? max:cnt;
}
printf("%d\n",max+);
}
return ;
}
poj 2606
#include <iostream>
#include <cstdio>
#include <memory.h>
using namespace std;
const int maxn=;
struct point
{
int x;
int y;
} pnt[maxn];
int main()
{
//freopen("in.txt","r",stdin);
int n,max,cnt;
while(cin >> n)
{
memset(pnt,,sizeof(pnt));
for(int i=;i<n;i++)
{
scanf("%d%d",&pnt[i].x,&pnt[i].y);
}
max=;
for(int i=;i<n;i++)
{
for(int j=i+;j<n;j++)
{
cnt=;
for(int k=j+;k<n;k++)
{
if(k==i || k==j)continue;
int left=(pnt[i].x-pnt[k].x)*(pnt[j].y-pnt[k].y);
int right=(pnt[j].x-pnt[k].x)*(pnt[i].y-pnt[k].y);
if(left==right)cnt++;
}
if(cnt>max)max=cnt;
}
}
cout << max+ << endl;
}
return ;
}
poj 2780
此题数据量比较大，同时虽然给的是3000ms，用n3算法也会超时，时间卡的紧，故一定要用n2lgn算法：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn = ;
const double eps = 1e-;
struct point
{
int x,y;
}node[maxn];
double k[maxn];
int n;
bool equal(double x,double y)
{
if(abs(x-y) <= eps)
{
return true;
}
return false;
}
int max(int a,int b)
{
return a > b ? a : b;
}
void read()
{
for(int i=;i<n;i++)
{
scanf("%d %d",&node[i].x,&node[i].y);
}
return;
}
void solve()
{
int ans = ;
for(int i=;i<n-;i++)
{
int top = ;
int tmp = ;
for(int j=i+;j<n;j++)
{
if(node[i].x == node[j].x)
{
tmp++;
}
else
{
k[top++] = (double)(node[j].y - node[i].y) / (node[j].x - node[i].x);
}
}
sort(k,k+top);
int cnt = ;
for(int j=;j<top;j++)
{
if(j < top- && equal(k[j],k[j+]))
{
cnt++;
}
else
{
tmp = max(tmp , cnt);
cnt = ;
}
}
ans = max(ans , tmp);
}
printf("%d\n",ans+);
return;
}
int main()
{
while(~scanf("%d",&n))
{
read();
solve();
}
return ;
}
注意对于每个点，都要求出当前对于此点的无斜率情况和最大斜率的数目的max
之后枚举每个点的上述max
之前wa了无数次，承蒙九龙大神给了一个平行四边形的测试数据才豁然开朗，同时当时对与斜率不存在的情况也没有依点而分析，造成错误在所难免，下附原来的wrong answer 代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <memory.h>
using namespace std;
const int maxn=;
double s[+];
struct location_
{
int x;
int y;
}l[maxn];
double slope(int m,int n)
{
double ans=(double)(l[m].y-l[n].y)/(double)(l[m].x-l[n].x);
return ans;
}
int main()
{
//freopen("in.txt","r",stdin);
int n;
while(cin >> n)
{
memset(l,,sizeof(l));
memset(s,0.0,sizeof(s));
int k=-;
int slo_cnt=;
for(int i=;i<=n;i++)
{
scanf("%d%d",&l[i].x,&l[i].y);
}
for(int i=;i<=n-;i++)
{
for(int j=i+;j<=n;j++)
{
if((l[i].x!=l[j].x))
{
k++;
s[k]=slope(i,j);
}
else
slo_cnt++;
}
}
for(int i=;i<=;i++)
{
if(i*(i-)/==slo_cnt)
{
slo_cnt=i;
break;
}
}
// cout << slo_cnt << ">>"<< endl;
// for(int i=0;i<=k-1;i++)
// {
// cout << i << ' ' <<s[i] << endl;
// }
sort(s,s+k);
// for(int i=0;i<=k-1;i++)
// {
// cout << i << ' ' <<s[i] << endl;
// }
int cnt=;
int max=;
for(int i=;i<=k-;i++)
{
if(fabs(s[i]-s[i-])<=0.00000001)
{
cnt++;
if(max<cnt)max=cnt;
}
else cnt=;
}
max++;
// cout << "dsdsdsds"<< " " <<max << endl;
for(int i=;i<=;i++)
{
if(i*(i-)/==max)
{
max=i;
break;
}
}
// cout << max<<" max " << endl;
// cout << slo_cnt << " slo_cnt "<<endl;
if(slo_cnt>max)max=slo_cnt;
cout << max << endl;
}
return ;
}