HDU 4036問題を保存して、数論の難度:1

1366 ワード

http://acm.hdu.edu.cn/showproblem.php?pid=4036
最初は斜め投げが必要だと思いましたが、エネルギー保存の法則だけが必要ですか?最大速度の悪いジャガイモのスピードと一致しています。
 
#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

using namespace std;

const int maxn=1e3+3;

int n,m;

double w;

double x[maxn],y[maxn];

struct pt{

    double p,v,m;

}b[maxn];

void input(){

    scanf("%d%d%lf",&n,&m,&w);

    for(int i=0;i<n;i++)scanf("%lf%lf",x+i,y+i);

    for(int i=0;i<m;i++)scanf("%lf%lf%lf",&b[i].p,&b[i].v,&b[i].m);

    for(int i=0;i<m;i++)b[i].p+=x[0];

    for(int i=n-1;i>=0;i--)y[i]-=y[0];

}

double calc(){

    double ans=0;

    for(int i=0;i<n;i++){

        if(y[i]>0)ans=max(ans,sqrt(40*y[i]));

    }

    for(int i=0;i<m;i++){

        for(int j=0;j<n-1;j++){

            if(x[j]<=b[i].p&&x[j+1]>=b[i].p){

                double h=(y[j+1]-y[j])/(x[j+1]-x[j])*(b[i].p-x[j])+y[j];

                ans=max(ans,sqrt(40*h+b[i].v*b[i].v));

                break;

            }

        }

    }

    return ans;

}

int main()

{

    int T;

    scanf("%d",&T);

    for(int ti=1;ti<=T;ti++){

        input();

        double ans=calc();

        printf("Case %d: %.2f
",ti,ans); } return 0; }