Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

哇哇 求拯救

Posted by laiyifa at 2013-10-10 15:58:51 on Problem 3301
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator