| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
哇哇 求拯救#include<cstdio>
#include<cmath>
using namespace std;
const double pi=acos(-1.0);
const double eps=1e-12;
double x[40],y[40],left,right,mid1,mid2,ans;
int n,t;
double fun(double angle)
{
double lmin=1e20,lmax=-1e20,hmin=1e20,hmax=-1e20,l,h;
for(int i=0;i<n;i++)
{
l=x[i]*cos(angle)+y[i]*sin(angle);
h=x[i]*sin(angle)+y[i]*cos(angle);
lmin=lmin<l?lmin:l;
lmax=lmax>l?lmax:l;
hmin=hmin<h?hmin:h;
hmax=hmax>h?hmax:h;
}
l=lmax-lmin,h=hmax-hmin;
return l>h?l:h;
}
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%lf%lf",&x[i],&y[i]);
left=0,right=pi/2.0;
while(left+eps<right)
{
mid1=(left+right)/2;
mid2=(mid1+right)/2;
if(fun(mid1)>fun(mid2))
left=mid1;
else
right=mid2;
}
ans=fun(left);
ans*=ans;
printf("%.2f\n",ans);
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator