题目大意:给一些点,找出一条直线使尽可能多的点在这条直线上,求这条直线上点的个数。
以每一个点为原点进行枚举,求其它点的斜率,斜率相同则说明在一条直线上。对斜率排序,找出斜率连续相等的最大长度。
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define MAXN 700+10
#define PRECISION 10e-9 struct Point
{
int x, y;
}; Point point[MAXN];
double slope[MAXN]; int main()
{
#ifdef LOCAL
freopen("in", "r", stdin);
#endif
int N;
scanf("%d", &N);
char s[];
getchar();
gets(s);
while (N--)
{
int n = ; // the number of points
while (gets(s))
{
if (s[] == '\0') break;
sscanf(s, "%d%d", &point[n].x, &point[n].y);
n++;
}
int ans = ;
for (int i = ; i < n; i++)
{
int zero_cnt = , k = ;
for (int j = ; j < n; j++)
if (i != j)
{
if (point[i].x == point[j].x) zero_cnt++;
else
{
slope[k] = 1.0 * (point[j].y - point[i].y) / (point[j].x - point[i].x);
k++;
}
}
sort(slope, slope+k);
int same_cnt = , maxl = ;
for (int i = ; i <= k; i++)
{
if (i < k && fabs(slope[i] - slope[i-]) < PRECISION)
{
same_cnt++;
}
else
{
maxl = max(maxl, same_cnt);
same_cnt = ;
}
}
maxl = max(maxl, zero_cnt);
ans = max(ans, maxl+);
}
printf("%d\n", ans);
if (N) printf("\n");
}
return ;
}
开始WA了两次,各种纠结,也找不出什么问题,忽然想到会不会是精度设的太大了,从10e-6改成10e-9,然后抱着侥幸心理提交了,竟然AC了...这个...算是积累经验吧