poj 1054(注意审题和理解题意,只考虑超过三个脚印的青蛙,如果存在青蛙脚印,则必须是连续的,即按规律之前和之后都不能有空格)

#include<iostream>
#include<algorithm>
using namespace std;
typedef struct node{
    int x,y;
}Point;
Point point[5005];
int r,c,n;
int qcmp(const void*a,const void*b){
    Point *p1 = (Point*)a;
    Point *p2 = (Point*)b;
    if(p1->x>p2->x||(p1->x==p2->x&&p1->y>p2->y))return 1;
    if(p1->x==p2->x&&p1->y==p2->y)return 0;
    return -1;
}
int cmp(Point p1,Point p2){
    if(p1.x<p2.x||(p1.x==p2.x&&p1.y<p2.y))return true;
    return false;
}
bool isIn(int x,int y){
    if(x<=0||x>r||y<=0||y>c)return false;
    return true;
}
bool search(int x,int y){
    int mid,l = 0,r = n;
    while(l<=r){
        mid = (l+r)/2;
        if(point[mid].x==x&&point[mid].y==y)return true;
        if(point[mid].x<x||(point[mid].x==x&&point[mid].y<y))l = mid+1;
        else r = mid-1;
    }
    return false;
}
int main(){
    scanf("%d%d%d",&r,&c,&n);
    for(int i=0;i<n;i++){
        scanf("%d%d",&point[i].x,&point[i].y);
    }
//    sort(point,point+n,cmp);
    qsort(point,n,sizeof(Point),qcmp);
    int max_num = 0;
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            int x = point[j].x-point[i].x;
            int y = point[j].y-point[i].y;
            if(isIn(point[i].x-x,point[i].y-y)||
              !isIn(point[i].x+max_num*x,point[i].y+max_num*y))continue;
            int num = 0;
            for(int k=1;isIn(point[j].x+k*x,point[j].y+k*y);k++){
                if(search(point[j].x+k*x,point[j].y+k*y))num++;
                else{
                    num = 0;
                    break;
                }
            }
            max_num = max(num,max_num);
        }
    }
    if(max_num)max_num += 2;
    printf("%d\n",max_num);
    return 0;
} 

 

上一篇:七天学会Python基础-第一天1/4


下一篇:栈-1598-文件夹日志操作