957E Bertha 。 2022-05-28 02:39 96阅读 0赞 ## 题意: ## Arkady在一个有n架飞机的机场做交管员。飞机的移动可以看做是在一维坐标系上,Arkady的站台位于原点(0坐标)。第i架飞机位于xi x i 坐标,以速度vi v i 向站台移动(保证xi∗vi<0 x i ∗ v i < 0 ,即最终都会到达原点)。 飞机还会受到风速影响,若风速为vwind(不一定是正数或整数) v w i n d ( 不 一 定 是 正 数 或 整 数 ) ,飞机的速度将会变成vi\+vwind v i + v w i n d 。 风速的范围在\[−w,w\] \[ − w , w \] ,但是不能准确的测量,因为风速很小,严格小于任何飞机的速度绝对值。 飞机在经过站台的时候必须和Arkady联系。你的任务是帮助Arkady计算有多少对可能的(i,j) ( i , j ) ,飞机i和飞机j在风速的作用下会同时到达站台(不同的对,风速可以不同)。你可以假定风速是稳定的,并且可以持续很长时间。 ## 输入格式: ## 第一行2个整数n和w(1 ≤ n ≤ 100 000,0 ≤ w < 105) n 和 w ( 1 ≤ n ≤ 100 000 , 0 ≤ w < 10 5 ) 接下去n行,每行2个整数xi和vi(1 ≤ |xi| ≤ 105,w \+ 1 ≤ |vi| ≤ 105,xi⋅vi < 0) x i 和 v i ( 1 ≤ | x i | ≤ 10 5 , w + 1 ≤ | v i | ≤ 10 5 , x i · v i < 0 ) 描述第i架飞机的信息 输入保证不存在(i,j)使得xi=xj且vi=vj ( i , j ) 使 得 x i = x j 且 v i = v j ## 输出格式: ## 仅一个整数,表示最多有多少对(i,j) ( i , j ) 可能会同时到达站台 ## 样例: ## inputCopy 5 1 -3 2 -3 3 -1 2 1 -3 3 -5 output 3 inputCopy 6 1 -3 2 -2 2 -1 2 1 -2 2 -2 3 -2 output 9 ## Note ## 在第一个例子中,以下3对飞机满足要求: * (2, 5) passes the station at time 3 / 4 with vwind = 1 v w i n d = 1 ; * (3, 4) passes the station at time 2 / 5 with vwind= 1 / 2 v w i n d = 1 / 2 ; * (3, 5) passes the station at time 4 / 7 with vwind= − 1 / 4 v w i n d = − 1 / 4 . 在第二个例子中,3个具有负坐标的平面中的每一个飞机可以与其他3个飞机中的每一个形成有效对,总共9对。
还没有评论,来说两句吧...