欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

[UVALive] - 5816 Dhaka 2011 H - Treasure Hunt

程序员文章站 2022-05-21 23:31:13
...

考虑到四个人的移动对于重心偏移的贡献相同,故沿重心偏移方向贪心走即可。

#include<bits/stdc++.h>
using namespace std;
typedef long double Double;
const Double eps=1e-25;
inline Double sqr(Double x){return x*x;}
inline double ip(){double x;scanf("%lf",&x);return x;}
inline void op(Double x,char c){printf("%.12lf%c",(double)x,c);}

struct point
{
    Double x,y;
    point() {}
    point(Double a,Double b) : x(a),y(b){}
    void in(){x=ip();y=ip();}
    void out(){op(x,' ');op(y,'\n');}
    #define cp const point &
    friend point operator + (cp a,cp b){return point(a.x+b.x,a.y+b.y);}
    friend point operator - (cp a,cp b){return point(a.x-b.x,a.y-b.y);}
    friend point operator * (cp a,Double b){return point(a.x*b,a.y*b);}
    Double len(){return sqrt(sqr(x)+sqr(y));}
}p[10],mid1,mid2,lk;

inline point unit(cp a)
{
    Double len=sqrt(sqr(a.x)+sqr(a.y));
    return point(a.x/len,a.y/len);
}

Double tot;

inline Double find(cp a,cp b,cp c)
{
    Double fm=(c.x-b.x)*lk.y+(b.y-c.y)*lk.x;
    if (fabs(fm)<eps) return 1e100;
    Double t=((c.y-b.y)*a.x+(b.x-c.x)*a.y+c.x*b.y-b.x*c.y)/fm;
    return t;
}

inline Double move(point &a)
{
    Double t,g[4]={find(a,p[5],p[6]),find(a,p[6],p[7]),find(a,p[7],p[8]),find(a,p[8],p[5])};
    sort(g,g+4);
    if (g[2]>1e90) t=g[1];
    else t=g[2];
	t=max(min(t,tot),(Double)0);
    a=a+lk*t;
    return t;
}

inline bool zero(point x){return fabs(x.x)<eps && fabs(x.y)<eps;}

inline void solve()
{
    for (int i=1;i<9;i++) p[i].in();
    bool flag=1;
    for (int i=1;i<9;i++) if (!zero(p[i])) flag=0;
    if (flag) exit(0);
    mid1=mid2=point(0,0);
    for (int i=1;i<5;i++) mid1=mid1+p[i];
    for (int i=5;i<9;i++) mid2=mid2+p[i];
    tot=(mid2-mid1).len();
    if (tot<eps)
    {
        for (int i=1;i<5;i++) p[i].out();
        return;
    }
    lk=unit(mid2-mid1);
    for (int i=1;i<5;i++) tot-=move(p[i]);
    for (int i=1;i<5;i++) p[i].out();
}

int main()
{
    while (1) solve(),puts("");
}