SGU 331 Traffic Jam(離散化＋DP)

タイトルリンク:http://acm.sgu.ru/problem.php?contest=0&problem=331
題意:n個の滑走路が与えられ、各滑走路のパラメータは3個のai,bi,detiがあり、t時点でi番目の滑走路での速度がbi+ai*sin(t+deti)であることを示す.iからjに移行する費用はc*abs(i-j)である.総距離d.走り終わるdの最小時間を求めます.最初は1番レーンでした.
構想:滑走路転換時刻t:bi+ai*(t+deti)=bj+aj*sin(t+detj+c*abs(i-j))すべてのtを求め、その番号とする.f[i][j]は、時刻jがi滑走路を走る最大距離を示す.

#include <iostream>

#include <cstdio>

#include <string.h>

#include <algorithm>

#include <cmath>

#include <vector>

#include <queue>

#include <set>

#include <stack>

#include <string>

#include <map>





#define max(x,y) ((x)>(y)?(x):(y))

#define min(x,y) ((x)<(y)?(x):(y))

#define abs(x) ((x)>=0?(x):-(x))

#define i64 long long

#define u32 unsigned int

#define u64 unsigned long long

#define clr(x,y) memset(x,y,sizeof(x))

#define CLR(x) x.clear()

#define ph(x) push(x)

#define pb(x) push_back(x)

#define Len(x) x.length()

#define SZ(x) x.size()

#define PI acos(-1.0)

#define sqr(x) ((x)*(x))

#define MP(x,y) make_pair(x,y)

#define EPS 1e-10



#define FOR0(i,x) for(i=0;i<x;i++)

#define FOR1(i,x) for(i=1;i<=x;i++)

#define FOR(i,a,b) for(i=a;i<=b;i++)

#define DOW0(i,x) for(i=x;i>=0;i--)

#define DOW1(i,x) for(i=x;i>=1;i--)

#define DOW(i,a,b) for(i=a;i>=b;i--)

using namespace std;





void RD(int &x){scanf("%d",&x);}

void RD(i64 &x){scanf("%I64d",&x);}

void RD(u32 &x){scanf("%u",&x);}

void RD(double &x){scanf("%lf",&x);}

void RD(int &x,int &y){scanf("%d%d",&x,&y);}

void RD(i64 &x,i64 &y){scanf("%I64d%I64d",&x,&y);}

void RD(u32 &x,u32 &y){scanf("%u%u",&x,&y);}

void RD(double &x,double &y){scanf("%lf%lf",&x,&y);}

void RD(int &x,int &y,int &z){scanf("%d%d%d",&x,&y,&z);}

void RD(i64 &x,i64 &y,i64 &z){scanf("%I64d%I64d%I64d",&x,&y,&z);}

void RD(u32 &x,u32 &y,u32 &z){scanf("%u%u%u",&x,&y,&z);}

void RD(double &x,double &y,double &z){scanf("%lf%lf%lf",&x,&y,&z);}

void RD(char &x){x=getchar();}

void RD(char *s){scanf("%s",s);}

void RD(string &s){cin>>s;}





void PR(int x) {printf("%d
",x);}

void PR(i64 x) {printf("%I64d
",x);}

void PR(u32 x) {printf("%u
",x);}

void PR(double x) {printf("%.6lf
",x);}

void PR(char x) {printf("%c
",x);}

void PR(char *x) {printf("%s
",x);}

void PR(string x) {cout<<x<<endl;}



const int N=10;

const int M=50005;

vector<pair<int,double> > ans;

vector<double> T;

double f[N][M];

int path[N][M];

double det[N],c,d,maxtime;

int a[N],b[N],n;





void getctime(int i,int j)

{

    int k;

    double A,B,C,D,x,y,z,t,t1,t2;

    vector<double> V;

    x=a[i]*cos(det[i])-a[j]*cos(det[j]+c*abs(i-j));

    y=a[i]*sin(det[i])-a[j]*sin(det[j]+c*abs(i-j));

    z=b[i]-b[j];

    A=z*z-x*x;

    B=-2.0*x*y;

    C=z*z-y*y;

    if(fabs(A)+fabs(B)>EPS)

    {

        if(fabs(A)<EPS)

        {

            t=atan(-C/B);

            if(t<-EPS) t=t+PI;

            while(t<maxtime) V.pb(t),t+=PI;

        }

        else

        {

            D=B*B-4.0*A*C;

            if(D>-EPS)

            {

                D=sqrt(fabs(D));

                t1=0.5*(-B-D)/A;

                t2=0.5*(-B+D)/A;

                t=atan(t1);

                if(t<-EPS) t+=PI;

                while(t<maxtime) V.pb(t),t+=PI;

                t=atan(t2);

                if(t<-EPS) t+=PI;

                while(t<maxtime) V.pb(t),t+=PI;

            }

        }

    }

    for(k=0;k<SZ(V);k++)

    {

        if(fabs(z+x*sin(V[k])+y*cos(V[k]))<1e-5)

        {

            T.pb(V[k]);

            T.pb(V[k]+c*abs(i-j));

        }

    }

}



double getdist(double t,double x,int i)

{

    return b[i]*x+a[i]*(cos(t+det[i])-cos(t+det[i]+x));

}



double gettime(double t,double dis,int i)

{

    double low=0.0,high=2*d,mid;

    while(low-high<-EPS)

    {

        mid=(low+high)*0.5;

        if(getdist(t,mid,i)<dis) low=mid;

        else high=mid;

	}

    return mid;

}



int getnextpos(int low,int high,double value)

{

    int mid;

    while(low<=high)

    {

        mid=(low+high)>>1;

        if(T[mid]<value-EPS) low=mid+1;

        else if(T[mid]>value+EPS) high=mid-1;

        else return mid;

    }

    return -1;

}



void input()

{

    int i,j;

    scanf("%d%lf%lf",&n,&d,&c);

    maxtime=0;

    FOR1(i,n)

    {

        scanf("%d%d%lf",&a[i],&b[i],&det[i]);

        T.pb(c*(i-1));

        maxtime=max(maxtime,gettime(0,d,i));

    }

    FOR1(i,n) FOR1(j,n) if(i!=j) getctime(i,j);

    sort(T.begin(),T.end());

    T.erase(unique(T.begin(),T.end()),T.end());

}





int main()

{

    input();

    int i,j,k,x,y,ansI,ansJ;

    double temp,Min=1e20;

    FOR0(i,N) FOR0(j,M) f[i][j]=-2;

    f[1][0]=0.0;

    FOR0(j,SZ(T)) FOR1(i,n) if(f[i][j]>-EPS&&f[i][j]<=d)

    {

        temp=gettime(T[j],d-f[i][j],i);

        if(Min>T[j]+temp) Min=T[j]+temp,ansI=i,ansJ=j;

        FOR1(x,n) if(x!=i)

        {

            y=getnextpos(j+1,SZ(T)-1,T[j]+c*abs(x-i));

            if(y!=-1&&f[x][y]<f[i][j])

            {

                f[x][y]=f[i][j];

                path[x][y]=i;

            }

        }

        k=j+1;

        temp=getdist(T[j],T[k]-T[j],i);

        if(f[i][k]<f[i][j]+temp)

        {

            f[i][k]=f[i][j]+temp;

            path[i][k]=i;

        }

    }

    while(ansJ!=0)

    {

        if(path[ansI][ansJ]==ansI)

        {

            ansJ--;

            continue;

        }

        temp=T[ansJ]-c*abs(ansI-path[ansI][ansJ]);

        ans.pb(MP(ansI,temp));

        ansI=path[ansI][ansJ];

        while(T[ansJ]>temp) ansJ--;

    }

    printf("%.15f
",Min);

    printf("%d
",SZ(ans));

    for(i=SZ(ans)-1;i>=0;i--)

    {

        printf("%d %.15f
",ans[i].first,ans[i].second);

    }

    return 0;

}