首页 > 代码库 > POJ1054 枚举【STL__binary_search()_的应用】

POJ1054 枚举【STL__binary_search()_的应用】

①使用binary_search前要先保证有序

②binary_search函数仅返回true或false

③binary_search(first element, laste lment + 1, data to search)

 1 #include <stdio.h> 2 #include <string.h> 3 #include <math.h> 4 #include <iostream> 5 #include <algorithm> 6 using namespace std; 7 struct PLANT{ 8     int x, y; 9 };10 PLANT map[5001];11 int r, c, num;12 int max_num;13 14 bool operator < (const PLANT & p1, const PLANT & p2){15     if(p1.x == p2.x)    return p1.y < p2.y;16     return p1.x < p2.x;17 }18 19 int function(int dx, int dy, int x, int y){20     int flag = 2;21     while(x >= 1 && x <= r && y >= 1 && y <= c){22         PLANT temp;23         temp.x = x;24         temp.y = y;25         if(!binary_search(map, map+num, temp))  return 0;26         x += dx;27         y += dy;28         ++flag;29     }30     return flag;31 }32 int main(){33     int i, j, k, t;34     int num_x, num_y;35     int flag;36     scanf("%d%d",&r,&c);37     scanf("%d",&num);38     for(i = 0; i < num; ++i)    scanf("%d%d",&map[i].x,&map[i].y);39 40     sort(map, map+num);41     max_num = 2;42 43     for(i = 0; i < num; ++i){44         for(j = i + 1; j < num; ++j){45             int dx = map[j].x - map[i].x;46             int dy = map[j].y - map[i].y;47             int px = map[i].x - dx;48             int py = map[i].y - dy;49             if(px >= 1 && px <= r && py >= 1 && py <= c)    continue;50 51             if(map[i].x + max_num * dx > r)   continue;52             int pY = map[i].y + max_num * dy;53             if(pY > c || pY < 1)    continue;54 55             px = dx + map[j].x;56             py = dy + map[j].y;57             int flag = 2;58             while(px >= 1 && px <= r && py >= 1 && py <= c){59                 PLANT temp;60                 temp.x = px;61                 temp.y = py;62                 if(!binary_search(map, map+num, temp)){63                     flag = 0;64                     break;65                 }66                 px += dx;67                 py += dy;68                 ++flag;69             }70             max_num = max(max_num, flag);71         }72     }73     if(max_num == 2)    printf("0\n");74     else    printf("%d\n",max_num);75     return 0;76 }