TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P4642
  • 题目
  • P4642【PA2014】动漫展
    限制 : 时间限制 : 20000 MS   空间限制 : 265536 KB
    评测说明 : 2s,256m
    问题描述

    吉丽的漫展有n件手办和m名警卫。建立平面直角坐标系,每个手办和警卫都可以看做一个点。警卫们的目光都朝着y轴负方向,且都有相同大小的视角。警卫可以看见自己视角内(包括边界上的点)的所有手办,不用考虑视线的遮挡。

    你打算抢劫吉丽的漫展,但不可被警卫发现。为了实施这次抢劫计划,你可以事先贿赂某些警卫,让他们闭上眼睛。只要某件手办不在任何睁着眼睛的警卫的视野内,你就可以偷走它。你知道每件手办的价格,以及每位警卫需要接受多少钱的贿赂。如右图,图中黑点代表警卫,灰点代表手办,数字代表金额。

    你想知道自己的最大收益是多少。

    输入格式

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

    第二行两个整数w,h,表示每个警卫的视角的一半的正切值是w/h。(见配图)
        接下来n行,每行三个整数x[i],y[i],v[i],表示手办的坐标为(x[i],y[i]),价格为v[i]。
        接下来m行,格式同上,表示警卫的坐标为(x[i],y[i]),需接受贿赂的金额为v[i]。
        保证每个点最多只有一个手办或一个警卫。

    输出格式

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

    样例输入

    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

    样例输出

    6

    提示

    【样例1解释】

    见配图,贿赂3+6元,偷走2+8+4+1元,收益6元。

     

    1≤m,n≤200000 

    1≤w,h,v[i]≤10^9  

    -10^9≤x[i],y[i]≤10^9


    来源  BZOJ3716