http://poj.org/problem?id=1054
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #define maxn 5001 5 using namespace std; 6 7 int r,c,n,x2,y2; 8 bool vis[maxn][maxn]; 9 struct node 10 { 11 int x,y; 12 bool operator <(const node &a)const 13 { 14 return (x<a.x)||(x==a.x&&y<a.y); 15 } 16 }p[maxn*2]; 17 18 int main() 19 { 20 while(scanf("%d%d",&r,&c)!=EOF) 21 { 22 scanf("%d",&n); 23 memset(vis,false,sizeof(vis)); 24 for(int i=0; i<n; i++) 25 { 26 scanf("%d%d",&p[i].x,&p[i].y); 27 vis[p[i].x][p[i].y]=true; 28 } 29 sort(p,p+n); 30 int max1=2; 31 for(int i=0; i<n; i++) 32 { 33 for(int j=i+1; j<n; j++) 34 { 35 int x1=p[j].x-p[i].x; 36 int y1=p[j].y-p[i].y; 37 if(p[i].x-x1>=1&&p[i].x-x1<=r&&p[i].y-y1>=1&&p[i].y-y1<=c) continue; 38 if(!(p[i].x+max1*x1>=1&&p[i].x+max1*x1<=r&&p[i].y+max1*y1>=1&&p[i].y+max1*y1<=c)) continue; 39 int t1=1; 40 x2=p[j].x; y2=p[j].y; 41 while(x2>=1&&x2<=r&&y2>=1&&y2<=c) 42 { 43 if(!vis[x2][y2]) break; 44 if(vis[x2][y2]) {t1++;} 45 x2=x2+x1; 46 y2=y2+y1; 47 } 48 if(!(x2>=1&&x2<=r&&y2>=1&&y2<=c)) 49 max1=max(max1,t1); 50 } 51 } 52 if(max1<=2) printf("0 "); 53 else 54 printf("%d ",max1); 55 } 56 return 0; 57 }