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 |
同为o(n ^ 2 log(n)), sort可过,map会tle#include <stdio.h> #include <map> #include <algorithm> //#define MAP using namespace std; const int MAX = 700; int gcd(int a, int b) { if(a == 0 || b == 0) return 0; else { if(a < 0) a = -a; if(b < 0) b = -b; if(a < b) { int c = a; a = b; b = c; } int c = a % b; while(c > 0) { a = b; b = c; c = a % b; } return b; } } int main() { int n; while(scanf("%d", &n) && n) { int p[MAX][2]; for(int i = 0; i < n; i++) scanf("%d%d", &p[i][0], &p[i][1]); int max = 0; for(int i = 0; i < n; i++) { #ifdef MAP map<pair<int, int>, int> m; #else pair<int, int> dis[MAX]; int pos = 0; #endif int same = 0; for(int j = i + 1; j < n; j++) { int dx = p[i][0] - p[j][0]; int dy = p[i][1] - p[j][1]; if(dx == 0 && dy == 0) same++; else { int c = gcd(dx, dy); if(c == 0) { if(dx == 0 && dy != 0) dy = 1; else if(dy == 0 && dx != 0) dx = 1; } else if(c != 1 && c != -1) { dx /= c; dy /= c; } if(dx < 0) { dx = -dx; dy = -dy; } #ifdef MAP m[make_pair(dx, dy)]++; #else dis[pos++] = make_pair(dx, dy); #endif } } #ifdef MAP for(map<pair<int, int>, int>::iterator it = m.begin(); it != m.end(); it++) { if((*it).second + same > max) max = (*it).second + same; } #else sort(dis, dis + pos); int v = same; for(int i = 1; i < pos; i++) { if(dis[i] == dis[i - 1]) v++; else { if(max < v) max = v; v = same; } } if(max < v) max = v; #endif } #ifdef MAP printf("%d\n", max + 1); #else printf("%d\n", max + 2); #endif } } 时间浪费在算最大公约数上,不过比除法安全。但是map会tle实在让人惊讶 Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator