| ||||||||||
| 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