AOJ 2226: Psychic Accelerator

この記事は、AOJ-ICPC Advent Calendarの記事です。

軌道は線分と円弧からなる(円弧は自分で計算する必要がある)。少し考えると、始点と終点からminとかを使ってGreedyに各線分の端点における最大速度が決められることがわかる。
あとはそれに基づいて所要時間を計算する。

と簡単に書きましたが、物理苦手勢には問題の言ってること理解と物理計算がめちゃくちゃ大変でした…。円運動とはいったい何なんだ…。

#include<stdio.h>
#include<algorithm>
#include<math.h>
using namespace std;
int x1[41000];
int Y1[41000];
int x2[41000];
int y2[41000];
double r[41000];
double len[41000];
const double EPS = 1e-10;
const double INF = 1e+10;
const double PI = acos(-1);
Pt p1[41000];
Pt p2[41000];

double v[41000];
double gett(double a,double s,double v1,double v2){
    double vt=sqrt(a*s+(v1*v1+v2*v2)/2);
    //printf("%f %f\n",vt,(2*vt-v1-v2)/a);
    return (2*vt-v1-v2)/a;
}
int main(){
    int a,b;
    scanf("%d%d",&a,&b);
    for(int i=0;i<a;i++){
        scanf("%d%d%d%d",x1+i,Y1+i,x2+i,y2+i);
        p1[i]=Pt((double)x1[i],(double)Y1[i]);
        p2[i]=Pt((double)x2[i],(double)y2[i]);
    }
    for(int i=0;i<a-1;i++){
        if(iLL(p1[i],p2[i],p1[i+1],p2[i+1])==0){
            double d=(p2[i]-p1[i+1]).ABS();
            r[i]=d/2;
            len[i]=d*PI/2;
        }else{
            Pt p=pLL(p2[i],p2[i]+(p1[i]-p2[i])*Pt(0,1),p1[i+1],p1[i+1]+(p2[i+1]-p1[i+1])*Pt(0,1));
            r[i]=(p-p2[i]).ABS();
            double d=(p2[i]-p1[i+1]).ABS()/2;
            double th=asin(d/r[i])*2;
            if((p2[i]-p1[i]).dot(p1[i+1]-p2[i])<-EPS)th+=PI;
            len[i]=r[i]*th;
        }
    }
    double now=0;
    for(int i=0;i<a-1;i++){
        now=sqrt((p2[i]-p1[i]).ABS()*2*b+now*now);
        now=min(now,sqrt(r[i]*b));
        v[i+1]=now;
    }
    now=0;
    for(int i=a-1;i>0;i--){
        now=sqrt((p2[i]-p1[i]).ABS()*2*b+now*now);
        now=min(now,sqrt(r[i-1]*b));
        now=min(now,v[i]);
        v[i]=now;
    }
    //for(int i=0;i<=a;i++)printf("%f %f %f\n",v[i],r[i],len[i]);
    double ret=0;
    for(int i=0;i<a;i++){
        ret+=gett((double)b,(p2[i]-p1[i]).ABS(),v[i],v[i+1]);
        if(i<a-1){
            ret+=len[i]/v[i+1];
        }
    }
    printf("%.10f\n",ret);
}