题意:逆时针绕圈,问最长怎么走
https://vjudge.net/problem/POJ-1696
int sgn(double x) {
if(fabs(x) < eps)return 0;
else return x<0?-1:1;
}
struct Point {
double x,y;
int id;
Point() {};
Point (double x,double y):x(x),y(y) {}
Point operator+(Point B) {
return Point(x+B.x,y+B.y);
}
Point operator-(Point B) {
return Point(x-B.x,y-B.y);
}
Point operator/(double k) {
return Point(x/k,y/k);
}
bool operator == (Point B) {
return sgn(x-B.x)==0&&sgn(y-B.y)==0;
}
};
struct Line {
Point p1,p2;
Line() {}
Line(Point p1,Point p2):p1(p1),p2(p2) {}
};
typedef Point Vector;
double Dot(Vector A,Vector B) {
return A.x*B.x+A.y*B.y;
}
double Cross(Vector A,Vector B) {
return A.x*B.y-A.y*B.x;
}
double Distance(Point A,Point B) {
double xx = A.x - B.x;
double yy = A.y - B.y;
return sqrt(xx*xx+yy*yy);
}
int n;
int pos;
Point p[N];
bool cmp(Point a,Point b) {
double t=Cross(a-p[pos],b-p[pos]);
if(sgn(t)==0)return Distance(p[pos],a)<Distance(p[pos],b);
else if(sgn(t)<0)return false;
return true;
}
void work() {
scanf("%d",&n);
double x,y;
for(int i=0; i<n; i++) { //先找到左下角的点
scanf("%d%lf%lf",&p[i].id,&p[i].x,&p[i].y);
// if(p[i].x < p[0].x || (p[i].x == p[0].x
// && p[i].y < p[0].y))swap(p[0],p[i]);
//注意,先判最下面再判最左边,不然wa
if(p[i].y < p[0].y || (p[i].y == p[0].y && p[i].x < p[0].x))swap(p[i],p[0]);
}
pos =0 ;
for(int i=1; i<n; i++) {
sort(p+i,p+n,cmp);
pos++;
}
printf("%d",n);
for(int i=0;i<n;i++){
printf(" %d",p[i].id);
}
printf("\n");
}