poj1054The Troublesome Frog<DP>

链接 : http://poj.org/problem?id=1054

题意:

有一个r*c的方格，青蛙会以相同的向量v=(x,y)跳过，跳过的地方留下痕迹，青蛙在格子外哪里出发都有可能，问有最多有多少只青蛙;

思路:

先把点排序, 使其有序化, 然后枚举任意两点所在的直线, 看有多少点落在直线上, 求其最大值;

View Code

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <string>
 4 #include <cstring>
 5 #include <cmath>
 6 #include <algorithm>
 7 #include <cstdlib>
 8 using namespace std;
 9 const int M=5005;
10 int R, C, N, x, y;
11 struct Point
12 {
13     int x, y;
14     bool operator < ( const Point &a ) const {
15         if( x==a.x )
16             return y<a.y;
17         return x<a.x;    
18     }
19 }p[M];
20 
21 int cmp( const void *e1, const void *e2 )
22 {
23     Point *p1, *p2;
24     p1 = (Point*) e1;
25     p2 = (Point*) e2;
26     if ( p1->x == p2->x ) return( p1->y - p2->y );
27     return ( p1->x - p2->x );
28 }
29 int AC( Point po, int dX, int dY ){
30     Point plant;
31     int temp;
32     plant.x = po.x + dX;
33     plant.y = po.y + dY;
34     temp = 2;
35     while ( plant.x <= R && plant.x >= 1 && plant.y <= C && plant.y >= 1 ) {
36         if ( !bsearch(&plant, p, N, sizeof(Point),cmp) ) {  // 在所有点中二分查找该点是否存在. 
37             temp = 0;
38                break;
39         }
40         plant.x += dX;
41         plant.y += dY;
42         temp++;
43     }
44     return( temp );
45 }
46 
47 int main( )
48 {
49     while( scanf( "%d%d", &R, &C )==2 ){
50         scanf( "%d", &N );
51         for( int i=0; i<N; ++ i ){
52             scanf( "%d%d", &x, &y );
53             p[i]=(Point){x, y} ;
54         }
55         sort( p, p+N );
56         int dx, dy, px, py, max=2;
57         
58         for( int i=0; i<N-2; ++ i ){
59             for( int j=i+1; j<N-1; ++ j ){
60                 dx=p[j].x-p[i].x, dy=p[j].y-p[i].y;
61                 px=p[i].x-dx, py=p[i].y-dy;
62                 if ( px <= R && px >= 1 && py <= C && py >= 1 ) continue;// 没出去 , 不合题意 
63                 if( p[i].x+max*dx>R )break; //  当前点,到位置加上max倍的距离已经出界, 所以temp最大不超过max, 不会更新max 
64                 py = p[i].y + max * dy;
65                 if ( py > C || py < 1) continue; // 同上 
66                 int temp = AC( p[j], dx, dy );
67                 if ( temp > max )  max = temp;
68             }
69         }
70         if ( max == 2 ) max = 0;
71             printf("%d\n", max);    
72         
73     }  
74     return 0;
75 }