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 |
Re:鸟破题,数据太弱了,N分的错误解法都能混过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: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator