OI题库

Problem 3

雾雨魔理沙(marisa.cpp/c/pas)

题目描述

在幻想乡，雾雨魔理沙（きりさめ まりさ）
是住在魔法之森普通的黑魔法少女。话说最近魔理沙从香霖堂拿到了升级过后的的迷你八卦炉，她迫不及待地希望试试八卦炉的威力。在一个二维平面上有许多毛玉(一种飞行生物，可以视为点)，每个毛玉具有两个属性，分值value和倍率mul。八卦炉发射出的魔法炮是一条无限长的直线形区域，可以视为两条倾斜角为α的平行线之间的区域，平行线之间的距离可以为任意值，如下图所示：

蓝色部分上下两条长边之间就是这次八卦炉的攻击范围，在蓝色范围内的毛玉(红点)属于该此被击中的毛玉，如果一个毛玉刚好在边界上也视为被击中。毛玉击中以后就会消失，每次发射八卦炉得到分值是该次击中毛玉的分值和乘上这些毛玉平均的倍率，设该次击中的毛玉集合为S，则分值计算公式为:

    Score = SUM{value[i] | i 属于 S} * SUM{mul[i] | i 属于 S} / |S|

其中|S|表示S的元素个数。魔理沙将会使用若干次八卦炉，直到把所有毛玉全部击中。任意两次攻击的范围均不重叠。最后得到的分值为每次攻击分值之和。现在请你计算出能够得到的最大分值。

输入格式

第1行：1个整数N，表示毛玉个数

第2..N+1行：每行四个整数x, y, value, mul，表示星星的坐标(x,y)，以及value和mul

第N+2行：1个整数α，表示倾斜角角度，0°到180°

输出格式

第1行：1个实数，表示最大分值，保留三位小数

输入样例

3

1 3 3 1

2 1 2 2

3 4 2 1

45

输出样例

9.333

数据范围

对于60%的数据：1 <= N <= 500

对于100%的数据：1 <= N <= 2,000

-10,000 <= x,y <= 10,000

1 <= value,mul <= 100

注意

π = 3.1415926