[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("");
}
下一篇: 洛谷P2574 XOR的艺术