Oracle 还原历史统计信息
就是求点逆时针旋转的次序。
第一次选取最左下角的点。然后每次选取一个极角最小的点。
#include<iostream> #include<string.h> #include<algorithm> #include<stdio.h> #include<math.h> #include<stack> using namespace std; #define maxn 200000 #define eps 0.00001 #define zero(x) ((fabs(x)<eps)?0:x) #define INF 999999 #define LL long long #define mod 1000003 struct point { int x; int y; int index; } p[55],pp,ds; int chaji(point a,point b,point c,point d) { return (b.x-a.x)*(d.y-c.y)-(d.x-c.x)*(b.y-a.y); } int dis(point a,point b) { return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y); } int cmp(point a,point b) { int d=chaji(ds,a,ds,b); if(d!=0)return d>0; return dis(ds,a)<dis(ds,b); } int pan(point a,point b,point c) { if(chaji(a,b,b,c)>=0)return 1; return 0; } int main() { int T,i,ip,n; scanf("%d",&T); while(T--) { pp.x=INF; pp.y=INF; scanf("%d",&n); for(i=0; i<n; i++) { cin>>p[i].index>>p[i].x>>p[i].y; if(pp.y>p[i].y||(pp.y==p[i].y&&pp.x>p[i].x)) { ip=i; pp.x=p[i].x; pp.y=p[i].y; } } cout<<n; cout<<" "<<p[ip].index; swap(p[0],p[ip]); ds=p[0]; for(i=1;i<n;i++) { sort(p+i,p+n,cmp); ds=p[i]; cout<<" "<<ds.index; } cout<<endl; } return 0; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。