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

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

Posted by tiler at 2011-07-19 08:24:50 on Problem 3301
```#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: