bzoj#P1580. [Usaco2009 Hol]Cattle Bruisers 杀手游戏

[Usaco2009 Hol]Cattle Bruisers 杀手游戏

题目描述

自从卡门在弹珠游戏中被贝茜彻底击败,他一直在想找机会复仇。这会儿,他邀贝茜去玩一个电脑游戏。

游戏中,贝茜在 (bx,by)(b_x,b_y) 处开始行动,这时时刻为 00。她要试图逃离。她的速度为 (bvx,bvy)(b_{v_x},b_{v_y}) 每秒。

不幸的是,卡门为了复仇,放出 nn 个杀手追击贝茜。在 t=0t=0 时,杀手 ii 的位置是 (xi,yi)(x_i,y_i),他的速度是 (vxi,vyi)(v_{x_i},v_{y_i}) 每秒。

由于每个杀手配备了手枪,手枪的射程是 rr,也就是说贝茜要与这个杀手的距离保持超过 rr,否则有性命之虞。

然而,贝茜还有一件秘密武器:盾。但是,她不想过多地消耗盾的能量。所以,她想知道逃脱过程中,某一个时刻她在最多多少个杀手的射程内。当然这个时刻不一定是整数。要求答案精确到 10410^{-4}

输入格式

11 行:66 个整数: n,r,bx,by,bvx,bvyn,r,b_x,b_y,b_{v_x},b_{v_y}

2n+12\sim n+1 行:每行输入四个整数 xi,yi,vxi,vyix_i,y_i,v_{x_i},v_{y_i}

输出格式

第一行:一个整数,表示在逃脱过程中,某一个时刻最多有这个数量的杀手可以射杀贝茜。

3 1 0 0 0 2
0 -3 0 4
1 2 -1 1
1 -2 2 -1
2

样例说明

在时刻为 1.51.5 时,贝茜在点 (0,3)(0,3),三个杀手分别在 (0,3)(0,3)(0.5,3.5)(-0.5,3.5)(4,3.5)(4,-3.5)。前两个杀手在贝茜一个单位以内,但是第三个永远不会和贝茜在一个单位以内,所以最多有 22 个杀手。

数据规模与约定

对于 100%100\% 的数据,1n500001\le n \le 500001000bx,by,xi,yi1000-1000 \le b_x,b_y,x_i,y_i \le 10001r25001\leq r \leq 2500100bvx,bvy,vxi,vyi100-100\leq b_{v_x},b_{v_y},v_{x_i},v_{y_i} \leq 100

题目来源

Usaco 2009 Hol