三分

HDU 3400 Line belt

网上题解很多我就不多说了

最关键的一步WA了我两发了

煞笔了,就是如果其中一条直线十分接近甚至是一个点的时候就会出现BUG

所以应该用do while

下面是AC代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#define eps 1e-6

using namespace std;

class point
{
public:
    double x,y;
};

double p,q,z,ans;
point a,b,c,d;
double thtw(point k);

inline double cal(point a,point b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
void thon()
{
    point l=a,r=b,mid,midmid;
    do
    {
        mid.x=(l.x+r.x)/2;
        mid.y=(l.y+r.y)/2;
        midmid.x=(l.x+mid.x)/2;
        midmid.y=(l.y+mid.y)/2;
        double msum,mmsum;
        msum=cal(a,mid)/p+thtw(mid);
        mmsum=cal(a,midmid)/p+thtw(midmid);
        if(msum+eps<=mmsum)
            l=midmid;
        else r=mid;
        ans=min(msum,mmsum);
    }while(cal(l,r)>=eps);
}

double thtw(point k)
{
    point l=c,r=d,mid,midmid;
    double kao;
    do
    {
        mid.x=(l.x+r.x)/2;
        mid.y=(l.y+r.y)/2;
        midmid.x=(l.x+mid.x)/2;
        midmid.y=(l.y+mid.y)/2;
        double msum,mmsum;
        msum=cal(k,mid)/z+cal(mid,d)/q;
        mmsum=cal(k,midmid)/z+cal(midmid,d)/q;
        if(msum+eps<=mmsum)
            l=midmid;
        else r=mid;
        kao=min(msum,mmsum);
    }while(cal(l,r)>=eps);
    return kao;
}


int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        ans=0;
        scanf("%lf%lf%lf%lf%lf%lf%lf%lf",&a.x,&a.y,&b.x,&b.y,&c.x,&c.y,&d.x,&d.y);
        scanf("%lf%lf%lf",&p,&q,&z);
        thon();
        printf("%.2f\n",ans);
    }
    return 0;
}

发表评论

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