#P1333. Spoj231 The Zebra Crossing 过马路

    ID: 345 传统题 1000ms 512MiB 尝试: 5 已通过: 3 难度: 8 上传者: 标签>CF2400提高+/省选-扫描线离散化懒标记线段树二分查找

Spoj231 The Zebra Crossing 过马路

题目描述

一条宽度为 WW 的马路,NN 个人站在马路的某一边,00 时刻每个人都以自己的速率和方向开始过马路(运动的过程中,速率和方向不变)。保证这 NN 个人的初始位置两两不同。你可以任意选一个未被他人占据的实数位置作为起始点,一个速率(速率有最大值限制)和方向,从 00 时刻混在那 NN 个人中过马路(过马路的过程中的速率和方向不变),要求途中碰到的人尽可能的多(碰到的意思是,在某一时刻两个人的坐标相等,碰撞不会对方向速率造成任何影响)。给定 NN 个人的初始位置和他们过马路的速率方向,你混在这 NN 个人中,求出你最多能碰到多少人。

输入格式

第一行包含三个数,为人的个数 NN(1≤N≤2×1041\leq N\leq 2\times 10^4),马路宽度 WW(1≤W≤1031\leq W\leq 10^3),和你的速率最大值 VV(1≤V≤1031\leq V\leq 10^3)。

接下来 NN 行,每行三个数描述一个人,分别是初始位置 XX(−104≤X≤104-10^4\leq X\leq 10^4),过马路用的时间 TT(1≤T≤1031\leq T\leq 10^3)和过马路的角度 α\alpha(正数表示偏右,负数偏左,−5000≤α≤5000-5000\leq\alpha\leq 5000,单位是 160\dfrac 1{60} 度)。

输出格式

输出答案,表示你最多可以遇到多少人。

5 20 5
-20 10 2700
20 10 -2700
-5 1 4000
-4 1 4000
5 1 -4000
2