POJ 1054 The Troublesome Frog

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <cmath>
 5 #include <algorithm>
 6 using namespace std;
 7 struct node
 8 {
 9     int x,y;
10 } p[5001];
11 bool flag[5001][5001];
12 bool cmp(node a,node b)
13 {
14     if(a.x == b.x)
15         return a.y < b.y;
16     else
17         return a.x < b.x;
18 }
19 int main()
20 {
21     int r,c,i,j,n,ans,temp,x,y,tx,ty;
22     memset(flag,0,sizeof(flag));
23     scanf("%d%d",&r,&c);
24     scanf("%d",&n);
25     for(i = 0; i < n; i ++)
26     {
27         scanf("%d%d",&p[i].x,&p[i].y);
28         flag[p[i].x][p[i].y] = 1;
29     }
30     sort(p,p+n,cmp);
31     ans = 2;
32     for(i = 0; i < n; i ++)
33     {
34         for(j = i+1; j < n; j ++)
35         {
36             x = p[j].x - p[i].x;
37             y = p[j].y - p[i].y;
38             tx = p[j].x;
39             ty = p[j].y;
40             if(p[i].x-x <= r&&p[i].x-x >= 1&&p[i].y-y <= c&&p[i].y-y >= 1)
41             continue;
42             for(temp = 2;; temp ++)
43             {
44                 tx = tx+x;
45                 ty = ty+y;
46                 if(tx > r||tx < 1)
47                     break;
48                 if(ty > c||ty < 1)
49                     break;
50                 if(!flag[tx][ty])
51                 {
52                     temp = 0;//注意这里，SB啊。
53                     break;
54                 }
55             }
56             ans = max(ans,temp);
57         }
58     }
59     if(ans < 3)
60     printf("0
");
61     else
62     printf("%d
",ans);
63     return 0;
64 }