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 |
数据略弱 暴力搜索+少量剪枝 79ms#include <iostream> #include <stdio.h> using namespace std; int R, C, N; struct p{ int x, y; } points[5005]; bool operator<(p &p1, p &p2){ if(p1.x < p2.x) return 1; if(p1.x > p2.x) return 0; return p1.y < p2.y; } inline bool inRange(int x, int y){ return x >= 1 && x <= R && y >= 1 && y <= C; } inline int mx(int x, int y){ return x>y? x : y; } inline int mn(int x, int y){ return x<y? x : y; } void quickSort(p s[], int l, int r) { if (l < r) { int i = l, j = r; p x = s[l]; while (i < j) { while(i < j && !(s[j] < x)) j--; if(i < j) s[i++] = s[j]; while(i < j && s[i] < x) i++; if(i < j) s[j--] = s[i]; } s[i] = x; quickSort(s, l, i - 1); quickSort(s, i + 1, r); } } bool state[5001][5001] = {0}; int main() { scanf("%d%d%d", &R, &C, &N); for(int i = 0; i < N; i++){ int x, y; scanf("%d%d", &x, &y); points[i].x = x; points[i].y = y; state[x][y] = 1; } quickSort(points, 0, N-1); int mx = 0; for(int i = 0; i < N-1; i++){ int xi = points[i].x, yi = points[i].y; for(int j = i+1; j < N; j++){ int xj = points[j].x, yj = points[j].y; int xcha = xj-xi, ycha = yj-yi; if(xi + mx*xcha > R){ break; } int ttt = yi + mx*ycha; if(ttt > C || ttt < 1){ continue; } if(inRange(xi-xcha, yi-ycha)) continue; int limit = 2147483647; if(xj != xi) limit = (R-xi)/xcha; if(yj > yi) limit = mn(limit, (C-yi)/ycha); else if(yj < yi) limit = mn(limit, (yi-1)/(-ycha)); if(limit < 2) continue; int startx = xj, starty = yj; int k = 0; bool ky = 1; for(; k < limit-1; k++){ startx += xcha, starty += ycha; if(!state[startx][starty]){ ky = 0; break; } } if(ky){ mx = limit + 1; } } } printf("%d\n", mx); return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator