hdu 3532 极角排序
scturtle
posted @ 2010年9月26日 02:57
in algorithm
, 2151 阅读
今天的D题,才知道极角排序。。。
#include <iostream> #include <cstdio> #include <vector> #include <algorithm> #include <cmath> using namespace std; #define pi 3.141592653 double jijiao(double x,double y) { return atan2(x,y)*180/pi; } double p[1001][2]; int main() { #ifndef ONLINE_JUDGE freopen("in","r",stdin); #endif vector<double> jj; int n,i,j,k; double maxj,minj,nowj; while(scanf("%d",&n)&&n>0) { for(i=0;i<n;i++) scanf("%lf%lf",&p[i][0],&p[i][1]); maxj=0; for(i=0;i<n;i++) { minj=180;jj.clear(); for(j=0;j<n;j++) if(i!=j) jj.push_back(jijiao(p[j][0]-p[i][0],p[j][1]-p[i][1])); sort(jj.begin(),jj.end()); for(j=0;j<jj.size()-1;j++) { nowj=jj[j+1]-jj[j]; if(nowj+1e-8>180) nowj=360-nowj; minj=min(minj,nowj); //printf("%f\n",nowj); } nowj=jj[0]-jj[jj.size()-1]+360; if(nowj+1e-8>180) nowj=360-nowj; minj=min(minj,nowj); //printf("%f\n",nowj); maxj=max(maxj,minj); } printf("%.4f\n",maxj); } }