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 |
凸包都不是,水排序,诶,这么多人WA,太弱了吧#include<stdio.h> #include<string.h> #include<algorithm> #include<math.h> using namespace std; #define eps 1e-8 #define inf 1<<29 struct point { int x, y; }p[52]; int det(int x1, int y1, int x2, int y2) { return x1 * y2 - x2 * y1; } int cross(point o, point a, point b) { return det(a.x - o.x, a.y - o.y, b.x - o.x, b.y - o.y); } double f(int x) { return x * x * 1.0; } double dis(point a, point b) { return sqrt( f(a.x - b.x) + f(a.y - b.y) ); } bool cmp(point a, point b) { int tmp = cross(p[0], a, b); if(tmp > 0) return 1; if(tmp == 0 && dis(p[0], a) < dis(p[0], b) )return 1; return 0; } int main() { int i, j; int n = 0; //freopen("int.txt", "r", stdin); while( ~scanf("%d%d", &p[n].x, &p[n].y) ) { if(p[n].y < p[0].y) swap(p[0], p[n]); else if(p[n].y == p[0].y && p[n].x < p[0].x) swap(p[0], p[n]); n++; } sort(p + 1, p + n, cmp); for(i = 0; i < n; i++) if(p[i].x == 0.0 && p[i].y == 0.0){ j = i; break; } for(i = j; i < n; i++) printf("(%d,%d)\n", p[i].x, p[i].y); for(i = 0; i < j; i++) printf("(%d,%d)\n", p[i].x, p[i].y); } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator