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