poj 3630 trie
poj 1077 康托展开

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);
    }
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter