問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1054思路:
好題，枚舉 + 二分
枚舉所有可能路徑的前兩個點
要注意的是:
starting outside the paddy on one side and ending outside the paddy on the other side代碼:
1 /* enumerate the first two points for each possible path */
2 #include<stdio.h>
3 #include<stdlib.h>
4 #include<string.h>
5 #define MAX_NUM 5001
6 #define is_valid(x, y) ((x)>0 && (x)<=R && (y)>0 && (y)<=C)
7 int R, C;
8 int total;
9 struct Point {
10 int x, y;
11 } points[MAX_NUM];
12
13 /* from top to down, and left to right */
14 int
15 compare(const void *arg1, const void *arg2)
16 {
17 struct Point *a = (struct Point *)arg1;
18 struct Point *b = (struct Point *)arg2;
19 if(a->x == b->x)
20 return a->y - b->y;
21 return a->x - b->x;
22 }
23
24 void
25 init()
26 {
27 int i;
28 scanf("%d", &total);
29 for(i=0; i<total; i++)
30 scanf("%d %d", &points[i].x, &points[i].y);
31 qsort(points, total, sizeof(struct Point), compare);
32 }
33
34 void
35 solve()
36 {
37 int i, j, tmp, max = 0;
38 int diff_x, diff_y;
39 struct Point p1, p2, next;
40 struct Point *ptr;
41 for(i=0; i<total; i++) {
42 for(j=i+1; j<total; j++) {
43 tmp = 2;
44 p1 = points[i];
45 p2 = points[j];
46 diff_x = p2.x - p1.x;
47 diff_y = p2.y - p1.y;
48 if(is_valid(p1.x-diff_x, p1.y-diff_y)) /* starting outside */
49 continue;
50 if(!is_valid(p1.x+max*diff_x, p1.y+max*diff_y)) /* pruning */
51 continue;
52 next.x = p2.x + diff_x;
53 next.y = p2.y + diff_y;
54 while(is_valid(next.x, next.y)) {
55 if((ptr=(struct Point *)bsearch(&next, points, total, sizeof(struct Point), compare)) == NULL) {
56 tmp = 0; /* ending outside */
57 break;
58 }
59 ++tmp;
60 next.x += diff_x;
61 next.y += diff_y;
62 }
63 max = tmp>max ? tmp : max;
64 }
65 }
66 printf("%d\n", max>2 ? max : 0);
67 }
68
69 int
70 main(int argc, char **argv)
71 {
72 while(scanf("%d %d", &R, &C) != EOF) {
73 init();
74 solve();
75 }
76 }