BZOJ1857: [Scoi2010]传送带【三分】

1857: [Scoi2010]传送带

【题目描述】

传送门

【题解】

三分套三分,在每个线段上三分就可以了,我三分的是点的坐标(x,y),还可以三分这条线段的长度。

代码如下

#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
const double EXP=1e-6;
int Q,P,R;
double Ax,Ay,Bx,By,Cx,Cy,Dx,Dy;
double sqr(double x){return x*x;}
double _abs(double x){return x<0?-x:x;}
double getdis(double x,double y,double _x,double _y){return sqrt(sqr(x-_x)+sqr(y-_y));}
double C(double x){if(x==0) return 1e-9;else return x;}
double check(double Fx,double Fy,double Sx,double Sy){return getdis(Ax,Ay,Fx,Fy)/Q+getdis(Dx,Dy,Sx,Sy)/P+getdis(Fx,Fy,Sx,Sy)/R;}
double Fen(double Fx,double Fy){
    double Lx,Ly,Rx,Ry,mid1x,mid1y,mid2x,mid2y,Ansx=0,Ansy=0;
    for(Lx=Cx,Rx=Dx,Ly=Cy,Ry=Dy,mid1x=Lx+(Rx-Lx)/3,mid2x=Rx-(Rx-Lx)/3,mid1y=Ly+(Ry-Ly)/3,mid2y=Ry-(Ry-Ly)/3;_abs(Rx-Lx)>=EXP||_abs(Ry-Ly)>=EXP;mid1x=Lx+(Rx-Lx)/3,mid2x=Rx-(Rx-Lx)/3,mid1y=Ly+(Ry-Ly)/3,mid2y=Ry-(Ry-Ly)/3)
    if(check(Fx,Fy,mid1x,mid1y)<check(Fx,Fy,mid2x,mid2y)) Rx=mid2x,Ansx=mid1x,Ry=mid2y,Ansy=mid1y;else Lx=mid1x,Ansx=mid2x,Ly=mid1y,Ansy=mid2y;
    return check(Fx,Fy,Ansx,Ansy);
}
int main(){
    double Lx,Ly,Rx,Ry,mid1x,mid1y,mid2x,mid2y,Ansx=0,Ansy=0;
    scanf("%lf%lf%lf%lf%lf%lf%lf%lf%d%d%d",&Ax,&Ay,&Bx,&By,&Cx,&Cy,&Dx,&Dy,&Q,&P,&R);
    for(Lx=Ax,Rx=Bx,Ly=Ay,Ry=By,mid1x=Lx+(Rx-Lx)/3,mid2x=Rx-(Rx-Lx)/3,mid1y=Ly+(Ry-Ly)/3,mid2y=Ry-(Ry-Ly)/3;_abs(Rx-Lx)>=EXP||_abs(Ry-Ly)>=EXP;mid1x=Lx+(Rx-Lx)/3,mid2x=Rx-(Rx-Lx)/3,mid1y=Ly+(Ry-Ly)/3,mid2y=Ry-(Ry-Ly)/3)
    if(Fen(mid1x,mid1y)<Fen(mid2x,mid2y)) Rx=mid2x,Ansx=mid1x,Ry=mid2y,Ansy=mid1y;else Lx=mid1x,Ansx=mid2x,Ly=mid1y,Ansy=mid2y;
    printf("%.2lf\n",Fen(Ansx,Ansy));
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部