比赛 东方幻想乡 S2 评测结果 AAAAAAAAAA
题目名称 雾雨魔理沙 最终得分 100
用户昵称 王者自由 运行时间 0.101 s
代码语言 C++ 内存使用 0.41 MiB
提交时间 2012-08-08 20:22:24
显示代码纯文本
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 2000 + 10;
const double pi = 3.1415926 / 180.0;
struct pill {
    double x, y, h, v, m;
    bool operator <(const pill &u) const {
        return h > u.h;
    }
} a[N];
int n;
double alpha, k, f[N], v[N], m[N];
int main() {
    freopen("marisa.in", "r", stdin);
    freopen("marisa.out", "w", stdout);
    scanf("%d", &n);
    for(int i=0; i<n; i++)
        scanf("%lf %lf %lf %lf", &a[i].x, &a[i].y, &a[i].v, &a[i].m);
    scanf("%lf", &alpha);
    k = tan(alpha * pi);
    for(int i=0; i<n; i++)
        a[i].h = a[i].y - k * a[i].x;
    sort(a, a+n);
    //for(int i=0; i<n; i++)
    //    fprintf(stderr, "%d: %.2lf %.2lf %.2lf %.2lf %.2lf\n", i, a[i].x, a[i].y, a[i].h, a[i].v, a[i].m);
    for(int i=0; i<n; i++)
        v[i+1] = v[i] + a[i].v,
        m[i+1] = m[i] + a[i].m;
    for(int i=1; i<=n; i++) {
        f[i] = v[i] * m[i] / i;
        //fprintf(stderr, "%.0lf*%.0lf/%d=%.0lf\n", v[i], m[i], i, f[i]);
        for(int j=1; j<i; j++)
            f[i] = max(f[i], f[j] + (v[i]-v[j]) * (m[i]-m[j]) / (i-j));
        //fprintf(stderr, "%lf\n", f[i]);
    }
    printf("%.3lf\n", f[n]);
    return 0;
}