POJ 1118 Lining Up 水题一道

来源：http://poj.org/problem?id=1118

题意：给你n个点（n < 700），求最多有多少个点在一条直线上。

思路：饭后一水了，由于数据范围小，直接暴力，（n^3）复杂度，水过。

代码：

#include <iostream>#include <cstdio>#include <string.h>using namespace std;#define CLR(arr,val) memset(arr,val,sizeof(arr))struct point{int x,y;}pp[800];int flag[800];int main(){//freopen("1.txt","r",stdin);int n;while(scanf("%d",&n) &&n){  for(int i = 0; i < n; ++i)  scanf("%d%d",&pp[i].x,&pp[i].y);  int mmax = 0;  CLR(flag,0);  for(int i = 0; i < n; ++i){  for(int j = i + 1;j < n; ++j){  int s = 2;  int a = pp[j].x - pp[i].x;  int b = pp[j].y - pp[i].y;  for(int k = j + 1; k < n; ++k){     int c = pp[k].x - pp[j].x; int d = pp[k].y - pp[j].y; if(a * d == c * b) s++;  }  if(mmax < s)  mmax = s;  }  }  printf("%d\n",mmax);}return 0;}