2012-C08-team5-problem-G

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

#define x first
#define y second

typedef pair<int,int> PII;
typedef pair<double,double> PDD;
typedef pair<double,PDD> TPL;

double sqr(double x){return x*x;}

TPL gao(double xp, double yp, double vp, double vt,
        double tmin, double tmax, const vector<PII>& u){
    double lo=tmin,hi=tmax,t,xt,yt,sum;
    for(int c=0;c<100;c++){
        sum=0;
        t=(lo+hi)/2;
        xt=u.back().x;
        yt=u.back().y;
        for(size_t i=1;i<u.size();i++){
            double l=sqrt(sqr(u[i].x-u[i-1].x)+sqr(u[i].y-u[i-1].y));
            if(sum+l>=t*vt){
                double r=(t*vt-sum)/l;
                xt=u[i-1].x*(1-r)+u[i].x*r;
                yt=u[i-1].y*(1-r)+u[i].y*r;
                break;
            }else sum+=l;
        }
        double l=sqrt(sqr(xp-xt)+sqr(yp-yt));
        if((t-tmin)*vp>=l) hi=t; else lo=t;
    }
    return TPL(t,PDD(xt,yt));
}

int main(){
    int n,x[1000],y[1000],xt,yt,vt,xp,yp,vp;
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d%d",x+i,y+i);
    scanf("%d%d%d",&xt,&yt,&vt);
    vector<PII> l,r;
    for(int i=1;i<n;i++){
        int p=(xt-x[i])*(y[i]-y[i-1]);
        int q=(yt-y[i])*(x[i]-x[i-1]);
        if(p!=q) continue;
        l.push_back(PII(xt,yt));
        r.push_back(PII(xt,yt));
        for(int j=i-1;~j;j--) l.push_back(PII(x[j],y[j]));
        for(int j=i;j!=n;j++) r.push_back(PII(x[j],y[j]));
        break;
    }
    scanf("%d%d%d",&xp,&yp,&vp);
    double lt=0,rt=0,ans;
    for(size_t i=1;i<l.size();i++) lt+=sqrt(sqr(l[i].x-l[i-1].x)+sqr(l[i].y-l[i-1].y));
    for(size_t i=1;i<r.size();i++) rt+=sqrt(sqr(r[i].x-r[i-1].x)+sqr(r[i].y-r[i-1].y));
    TPL lz=gao(xp,yp,vp,vt,0,lt/=vt,l);
    TPL rz=gao(xp,yp,vp,vt,0,rt/=vt,r);
    ans=max(lt,rt);
    ans=min(ans,max(lz.x,gao(lz.y.x,lz.y.y,vp,vt,lz.x,rt,r).first));
    ans=min(ans,max(rz.x,gao(rz.y.x,rz.y.y,vp,vt,rz.x,lt,l).first));
    printf("%.12f\n",ans);
}
}}}

#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
typedef pair<double,PDD> TPL;
double sqr(double x){return x*x;}
TPL gao(double xp, double yp, double vp, double vt,
        double tmin, double tmax, const vector<PII>& u){
    double lo=tmin,hi=tmax,t,xt,yt,sum;
    for(int c=0;c<100;c++){
        sum=0;
        t=(lo+hi)/2;
        xt=u.back().x;
        yt=u.back().y;
        for(size_t i=1;i<u.size();i++){
            double l=sqrt(sqr(u[i].x-u[i-1].x)+sqr(u[i].y-u[i-1].y));
            if(sum+l>=t*vt){
                double r=(t*vt-sum)/l;
                xt=u[i-1].x*(1-r)+u[i].x*r;
                yt=u[i-1].y*(1-r)+u[i].y*r;
                break;
            }else sum+=l;
        }
        double l=sqrt(sqr(xp-xt)+sqr(yp-yt));
        if((t-tmin)*vp>=l) hi=t; else lo=t;
    }
    return TPL(t,PDD(xt,yt));
}
int main(){
    int n,x[1000],y[1000],xt,yt,vt,xp,yp,vp;
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d%d",x+i,y+i);
    scanf("%d%d%d",&xt,&yt,&vt);
    vector<PII> l,r;
    for(int i=1;i<n;i++){
        int p=(xt-x[i])*(y[i]-y[i-1]);
        int q=(yt-y[i])*(x[i]-x[i-1]);
        if(p!=q) continue;
        l.push_back(PII(xt,yt));
        r.push_back(PII(xt,yt));
        for(int j=i-1;~j;j--) l.push_back(PII(x[j],y[j]));
        for(int j=i;j!=n;j++) r.push_back(PII(x[j],y[j]));
        break;
    }
    scanf("%d%d%d",&xp,&yp,&vp);
    double lt=0,rt=0,ans;
    for(size_t i=1;i<l.size();i++) lt+=sqrt(sqr(l[i].x-l[i-1].x)+sqr(l[i].y-l[i-1].y));
    for(size_t i=1;i<r.size();i++) rt+=sqrt(sqr(r[i].x-r[i-1].x)+sqr(r[i].y-r[i-1].y));
    TPL lz=gao(xp,yp,vp,vt,0,lt/=vt,l);
    TPL rz=gao(xp,yp,vp,vt,0,rt/=vt,r);
    ans=max(lt,rt);
    ans=min(ans,max(lz.x,gao(lz.y.x,lz.y.y,vp,vt,lz.x,rt,r).first));
    ans=min(ans,max(rz.x,gao(rz.y.x,rz.y.y,vp,vt,rz.x,lt,l).first));
    printf("%.12f\n",ans);
}