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

## Re:鸟破题,数据太弱了,N分的错误解法都能混过

Posted by xiefubao at 2014-01-26 22:50:52 on Problem 3301
In Reply To:鸟破题,数据太弱了,N分的错误解法都能混过 Posted by:tiler at 2011-07-19 08:24:50
```> #include <iostream>
> #include <stdio.h>
> #include <math.h>
> #define MAX 1000000000
> #define MIN -1000000000
> #define PI acos (-1.0)
> using namespace std;
> double x[50],y[50];
> int main() {
> 	long t,n,j,i;
> 	scanf("%d",&t);
>
> 	while(t--) {
> 		scanf("%d",&n);
> 		for(j=0;j<n;j++) {
> 			scanf("%lf%lf",&x[j],&y[j]);
> 		}
> 		double ans = MAX;
> 		int Time = 30;//细分层数
>
> 		int interval = 1000;//细分区间数
>
> 		//from 0 to 90度
> 		double sum = PI/2;//总区间
>
> 		double steplen = sum / ((double)interval-2);
>
> 		double st = 0;
>
> 		double tmp = 0;
> 		while(Time--) {
>
>
> 			for(i=0;i<interval;i++)	{
>
> 				double getSin=sin(tmp); double getCos=cos(tmp);
> 				double down = MAX,left=MAX,up=MIN,right=MIN;
> 				for(j=0;j<n;j++)
> 				{
> 					double nx=x[j]*getCos-y[j]*getSin;
> 					double ny=y[j]*getCos+x[j]*getSin;
> 					if(nx<left) left=nx;
> 					if(nx>right) right=nx;
> 					if(ny<down) down=ny;
> 					if(ny>up) up=ny;
> 				}
> 				double border=right-left;
> 				border=(up-down)>border?(up-down):border;
>
> 				if(border<ans) {
> 					ans=border,st=tmp;
> 				}
> 				tmp += steplen;
> 			}
> 			tmp = st-steplen; //下一层进行该最优值的前后细分
> 			steplen = ((2*steplen)/(interval-2));
> 		}
> 		printf("%.2lf\n",ans * ans);
> 	}
> 	return 0;
> }
```

Followed by: