| ||||||||||
| 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