> rt
贴代码
Source Code

Problem: 3011  User: Los_Angelos_Laycurse 
Memory: 368K  Time: 3375MS 
Language: C++  Result: Accepted 

Source Code 
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<stdio.h>
#include<cmath>
#include<map>
using namespace std;
double ans1,ans2,arg1,arg2,eps=1e-10,arg[100000],value,ta,ax,pi=acos(-1.000);
double res1[10000],res2[10000];
struct segment
{
   double b1,b2;
   bool operator <(const segment &temp)const
   {
        return b1<temp.b1;
   }
};
segment seg[20000];
struct point
{
    double x,y;
};
point a[111];
int cnt,ncnt;
int gcd(int a,int b)
{
    int temp;
    while(b!=0)
    {
        temp=a%b;
        a=b;
        b=temp;
    }
    return a;
}
int main()
{
    int n,i,j,s,p,q,id,tst=0;
    cnt=0;
    for(i=-30;i<=30;i++)
       for(j=0;j<=30;j++)
       {
           if(gcd(abs(i),abs(j))>1)
              continue;
           if(j==0)
              arg[cnt++]=pi/2;
           else
           {
               arg[cnt]=atan((double)i/(double)j);
               if(arg[cnt]<0)
                 arg[cnt]+=pi;
               cnt++;
           }   
       }
    while(scanf("%d",&n)&&n!=0)
    {
        for(i=0;i<n;i++)
           scanf("%lf%lf",&a[i].x,&a[i].y);
        ncnt=cnt;
        for(i=0;i<n;i++)
          for(j=i+1;j<n;j++)
          {
              if(a[i].x==a[j].x)
                 arg[ncnt]=pi/2.00;
              else
              {
                  arg[ncnt]=atan((a[i].y-a[j].y)/(a[i].x-a[j].x));
                  if(arg[ncnt]<0)
                     arg[ncnt]+=pi;
                  arg[ncnt]=pi-arg[ncnt];
              }
              ncnt++;
              double x0=(a[i].x+a[j].x)/2.00,y0=(a[i].y+a[j].y)/2.00,dist;
              dist=sqrt((x0-a[j].x)*(x0-a[j].x)+(y0-a[j].y)*(y0-a[j].y));
              if(dist<1.00)
                 dist=1.00;
              double theta1=asin(1.000/dist),theta2,theta;
              if(a[i].x==a[j].x)
                 theta2=pi/2.00;
              else
                 theta2=atan((a[i].y-a[j].y)/(a[i].x-a[j].x));
              if(theta2<0)
                 theta2+=pi;
              theta=theta1+theta2;
              if(theta>pi)
                 theta-=pi;
              theta=pi-theta;
              arg[ncnt++]=theta;
              theta=theta2-theta1;
              if(theta<0)
                 theta+=pi;
              theta=pi-theta;
              arg[ncnt++]=theta;
          }
        ans1=0;
        ans2=1000000000;
        for(i=0;i<ncnt;i++)
        {
            double v1;
            ta=tan(pi-arg[i]);
            v1=sqrt(1+ta*ta); 
            for(j=0;j<n;j++)
            {
               double b=a[j].y-ta*a[j].x;
               seg[j].b1=b-v1;
               seg[j].b2=b+v1;
            }
            sort(seg,seg+n);
            ax=seg[0].b2;
            value=id=0;
            for(j=1;j<n;j++)
            {
               if(seg[j].b1>ax)
               {
                  value+=(ax-seg[id].b1)/v1;
                  id=j;
               }
               if(seg[j].b2>ax)
                  ax=seg[j].b2;
            }
            value+=(ax-seg[id].b1)/v1;
            if(ans1<value)
            {
                ans1=value;
                arg1=arg[i];
            }
            if(ans2>value)
            {
                ans2=value;
                arg2=arg[i];
            }
        }
        res1[tst]=arg2;
        res2[tst++]=arg1;
    }
    for(i=0;i<tst;i++)
      printf("%.20lf\n%.20lf\n",res1[i],res2[i]);
    //system("pause");
    return 0;
}