| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
对这个判定条件有疑问 附AC代码#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
using namespace std;
typedef struct{
int x, y;
}Cord;
Cord map_t[5002];
int col, row;
int compare_a(const void* a, const void* b)
{ //按照行号排序,行号相等时按列号升序排序
Cord *p, *q;
p = (Cord*)a;
q = (Cord*)b;
if (p->x == q->x) return (p->y - q->y);
else return (p->x - q->x);
}
int binary_search(Cord next, int begin, int end){
if(begin > end)
return -1;
int mid = (begin + end) / 2;
Cord tmp = map_t[mid];
if(compare(&tmp, &next) < 0)
return binary_search(next, mid + 1, end);
else if(compare(&tmp, &next) > 0)
return binary_search(next, begin, mid - 1);
else
return mid;
return -1;
}
int find_path(Cord st, int dx, int dy, int begin, int size){
int step = 2;
int inx = begin;
Cord tmp;
tmp.x = st.x + dx;
tmp.y = st.y + dy;
while (tmp.x>=1 && tmp.x<=col && tmp.y>=1 & tmp.y<=row) { // 为什么一定要判断x大于等于1 不是题目有限定吗 一定会在1开始的
if(binary_search(tmp, 1, size) < 0)
return 0;
tmp.x += dx;
tmp.y += dy;
++step;
}
return step;
}
int main(){
int n = 0;
int i = 1;
scanf("%d %d", &col, &row);
cin>>n;
for(int i = 1; i <= n; ++i){
scanf("%d %d", &(map_t[i].x), &(map_t[i].y));
}
qsort(map_t + 1, n, sizeof(Cord), compare);
int max_step = 2;
for(int i = 1; i <= n - 1; ++i){
for(int j = i + 1; j <= n; ++j){
int dx, dy;
dx = map_t[j].x - map_t[i].x;
dy = map_t[j].y - map_t[i].y;
if(map_t[i].x - dx >= 1 && map_t[i].y - dy >= 1
&& map_t[i].x - dx <= col && map_t[i].y - dy <= row)
continue;
if(map_t[j].x + (max_step - 1) * dx > col)
break;
int y0 = map_t[i].y + max_step * dy;
//if (y0 > row || y0 < 1) continue;
int tmp = find_path(map_t[j], dx, dy, j, n);
if(tmp > max_step)
max_step = tmp;
}
}
if(max_step == 2)
max_step = 0;
cout<<max_step<<endl;
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator