cogs 999. [東方S2]雾雨魔理沙

摸你傻赛高！！
/*

    cogs 999. [東方S2]雾雨魔理沙

    原来以为是一道计算几何的题

    可是细细一想发现。。

    这就是一道dp

    由于给定了斜率

    每个点的b值也可以确定了(y = kx + b)

    按照b值排序

    后区间dp搞搞就好了

*/

#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdio>

#include <cmath>

#define PI 3.1415926

void read (int &now)

{

    register char word = getchar ();

    int temp = ;

    for (now = ; !isdigit (word); word = getchar ())

        if (word == '-')

            temp = ;

    for (; isdigit (word); now = now *  + word - '', word = getchar ());

    if (temp)

        now = -now;

}

double k;

struct Point

{

    int x, y;

    int value, mul;

    Point (int __x, int __y, int __v, int __m) : x (__x), y (__y), value (__v), mul (__m){}

    Point () {}

    bool operator < (const Point &now) const

    {

        return (this->y - (this->x * k)) < (now.y - (now.x * k));

    }

};

#define Max 2008

Point point[Max];

int _sum[Max], _mul[Max];

double dp[Max];

inline double max (double a, double b)

{

    return a > b ? a : b;

}

#define Cogs

int main (int argc, char *argv[])

{

#ifdef Cogs

    freopen ("marisa.in", "r", stdin);

    freopen ("marisa.out", "w", stdout);

#endif

    int N;

    read (N);

    register int i, j;

    for (i = ; i <= N; ++ i)

        read (point[i].x), read (point[i].y), read (point[i].value), read (point[i].mul);

    scanf ("%lf", &k);

    k = tan (k /  *  * PI);

    std :: sort (point + , point +  + N);

    for (i = ; i <= N; ++ i)

    {

        _sum[i] = _sum[i - ] + point[i].value;

        _mul[i] = _mul[i - ] + point[i].mul;

        dp[i] = ;

        for (j = ; j <= i; ++ j)

            dp[i] = max (dp[i], dp[j - ] + double(_sum[i] - _sum[j - ]) * (_mul[i] - _mul[j - ]) / (i - j + ));

    }

    printf ("%.3lf", dp[N]);

    return ;

}