#P4251. [PA2014]Muzeum

    ID: 3468 传统题 1000ms 256MiB 尝试: 60 已通过: 37 难度: 8 上传者: 标签>难度分类提高+/省选-模拟与实现技巧坐标变换图论最小割建模最大流最小割定理计算几何扫描线贪心排序贪心交换论证数据结构有序集合事件同坐标排序CF2500

[PA2014]Muzeum

[PA2014] Muzeum

题目描述

吉丽的漫展有 nn 件手办和 mm 名警卫。手办和警卫都视作平面上的点。每名警卫面朝 yy 轴负方向,视野的大小相同。警卫能看见视野内及边界上的所有手办,手办和其他警卫均不会挡住视线。

你可以贿赂若干名警卫,让他们闭上眼睛。只要某件手办不在任何未被贿赂的警卫的视野内,你就可以偷走它。求能获得的最大净收益,即偷走的手办总价值减去贿赂费用。

输入格式

第一行两个整数 n,mn,m,分别表示手办和警卫的数量。

第二行两个整数 w,hw,h,表示警卫半视角的正切为 wh\dfrac{w}{h}。

接下来 nn 行,每行三个整数 xi,yi,vix_i,y_i,v_i,表示一件手办位于 (xi,yi)(x_i,y_i),价值为 viv_i。再接下来 mm 行,格式相同,分别表示警卫的位置和贿赂这名警卫的费用。

保证每个位置最多有一个手办或一名警卫。

输出格式

输出一行一个整数,表示最大净收益。

样例 #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

样例说明

警卫的视野、手办的位置与金额

警卫的视角略大于 67∘67^\circ。贿赂费用分别为 33 和 66 的两名警卫后,可以偷走四件手办,价值共 2+8+4+1=152+8+4+1=15,净收益为 15−(3+6)=615-(3+6)=6。

数据规模与约定

1≤n,m≤2×1051\le n,m\le2\times10^5,1≤w,h≤1091\le w,h\le10^9,−109≤xi,yi≤109-10^9\le x_i,y_i\le10^9,1≤vi≤1091\le v_i\le10^9。

题目和样例图来源见 Potyczki Algorytmiczne 2014 原题.