三分

HDU 3400 Line belt

Posted on

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

最关键的一步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;
}
二分

HDU 4355 Party All the Time

Posted on

暑假集训选拔马上就要开始了

挺虚的,就临时抱一下佛脚

把以前没有写的周练补一下,从最开始补起,也就是二分三分

没想到一下子就A了,说明还是有点长进的,哈哈,可喜可贺,可喜可贺

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

using namespace std;

inline double cal(double a,double b)
{
    if(a<0) a=-a;
    return a*a*a*b;
}

int main()
{
    int t;
    scanf("%d",&t);
    for(int k=1;k<=t;k++)
    {
        int n;
        double x[50100],w[50100],l=1000000,r=-1000000,mid,midmid,ans=0;
        scanf("%d",&n);
        for(int i=0;i<n;i++)
        {
            scanf("%lf%lf",&x[i],&w[i]);
            l=min(l,x[i]);
            r=max(r,x[i]);
        }
        while(eps+l<=r)
        {
            mid=(l+r)/2;
            midmid=(l+mid)/2;
            double msum=0,mmsum=0;
            for(int i=0;i<n;i++)
            {
                msum+=cal(mid-x[i],w[i]);
                mmsum+=cal(midmid-x[i],w[i]);
            }
            if(msum+eps<mmsum) l=midmid;
            else r=mid;
            ans=min(msum,mmsum);
        }
        printf("Case #%d: %.0f\n",k,ans);
    }
    return 0;
}