#P4251. [PA2014]Muzeum
[PA2014]Muzeum
[PA2014] Muzeum
题目描述
吉丽的漫展有 件手办和 名警卫。手办和警卫都视作平面上的点。每名警卫面朝 轴负方向,视野的大小相同。警卫能看见视野内及边界上的所有手办,手办和其他警卫均不会挡住视线。
你可以贿赂若干名警卫,让他们闭上眼睛。只要某件手办不在任何未被贿赂的警卫的视野内,你就可以偷走它。求能获得的最大净收益,即偷走的手办总价值减去贿赂费用。
输入格式
第一行两个整数 ,分别表示手办和警卫的数量。
第二行两个整数 ,表示警卫半视角的正切为 。
接下来 行,每行三个整数 ,表示一件手办位于 ,价值为 。再接下来 行,格式相同,分别表示警卫的位置和贿赂这名警卫的费用。
保证每个位置最多有一个手办或一名警卫。
输出格式
输出一行一个整数,表示最大净收益。
样例 #1
样例输入 #1
5 3
2 3
2 6 2
5 1 3
5 5 8
7 3 4
8 6 1
3 8 3
4 3 5
5 7 6
样例输出 #1
6
样例说明

警卫的视角略大于 。贿赂费用分别为 和 的两名警卫后,可以偷走四件手办,价值共 ,净收益为 。
数据规模与约定
,,,。
题目和样例图来源见 Potyczki Algorytmiczne 2014 原题.