#P2903. [USACO08MAR] The Loathesome Hay Baler S

    ID: 1950 Type: RemoteJudge 1000ms 125MiB Tried: 0 Accepted: 0 Difficulty: 3 Uploaded By: Tags>模拟搜索2008USACO广度优先搜索,BFS

[USACO08MAR] The Loathesome Hay Baler S

题目描述

Farmer John has purchased the world's most loathesome hay baler. Instead of having a drive-roller that drives maybe an idler roller that drives the power take-off for the baler, it has N rollers (2 <= N <= 1050) which drive and are driven by various rollers.

FJ has meticulously cataloged data for each roller i: X_i,Y_i are the center of the roller (-5000 <= X_i <= 5000; -5000 <= Y_i <= 5000); R_i is the roller's radius (3 <= R_i <= 800). The drive-roller is located at 0,0; the baler power take-off is located at X_t,Y_t (numbers supplied in the input).

The drive-roller turns clockwise at 10,000 revolutions per hour. Your job is to determine the speeds of all the rollers that are in the power-train: from the drive-roller through the power take-off roller. Rollers that do not transfer power to the take-off roller are to be ignored. A roller of radius Rd that is turning at S rph and driving another roller of radius Rx will cause the second roller to turn at the speed -S*Rd/Rx (where the sign denotes whether the roller is turning clockwise or counterclockwise (anticlockwise for our British friends)).

Determine the power-train path and report the sum of the absolute values of all those rollers' speeds. All the rollers in the input set except the driver-roller are driven by some other roller; power is never transferred to a roller from more than one other roller.

Report your answer as an integer that is the truncated value after summing all the speeds.

输入格式

* Line 1: Three space-separated integers: N, X_t, and Y_t

* Lines 2..N+1: Line i+1 describes roller i's properties: X_i, Y_i, and R_i

输出格式

* Line 1: A single integer that is the truncated version of the sum of the absolute value of the speeds of the rollers in the power-train including the drive-roller, all the driven rollers, and the power take-off roller.

题目大意

Farmer John 新买的干草打包机的内部结构大概算世界上最混乱的了,它不像普通的机器一样有明确的内部传动装置,而是 NN 个齿轮互相作用,每个齿轮都可能驱动着多个齿轮。 FJ 记录了对于每个齿轮 ii,记录了它的 33 个参数,以一个三元组 (x,y,r)(x,y,r) 表示,xxyy 表示齿轮中心的位置坐标,rr 表示该齿轮的半径。

驱动齿轮的位置为 (0,0)(0,0),并且 FJ 也知道最终的工作齿轮位于 (Xt,Yt)(X_t,Y_t)。 驱动齿轮顺时针转动,转速为 10,00010,000 转/小时。你的任务是,确定传动序列中所有齿轮的转速。传动序列的定义为,能量由驱动齿轮传送到工作齿轮的过程中用到的所有齿轮的集合。对能量传送无意义的齿轮都应当被忽略。

在一个半径为 RdR_d,转速为 SS 转/每小时的齿轮的带动下,与它相接的半径为 RxR_x 的齿轮的转速将为 S×RdRx-S\times \frac{R_d}{R_x} 转/小时。SS 前的负号的意思是,一个齿轮带动的另一个齿轮的转向会与它的转向相反。

FJ 只对整个传动序列中所有齿轮速度的绝对值之和感兴趣,你的任务也就相应转化成求这个值。机器中除了驱动齿轮以外的所有齿轮都被另外某个齿轮带动,并且不会出现 22 个不同的齿轮带动同一个齿轮的情况。

输入格式

第一行,三个整数,分别代表 N,Xt,YtN,X_t,Y_t

22 行到第 N+1N+1 行,每行三个整数,代表一个三元组 (x,y,r)(x,y,r)

输出格式

输出共一行,一个整数,代表整个传动序列中所有齿轮速度的绝对值之和。

4 32 54 
0 0 10 
0 30 20 
32 54 20 
-40 30 20 

20000 

提示

2N10502 \leq N \leq 10505000x,y5000-5000 \leq x,y \leq 50003r8003 \leq r \leq 800

Four rollers: the drive-roller at 0,0 with radius 10. It drives the roller above it at 0,30 with radius 20. That roller drives both the power take-off roller at 32,54 (r=20) and a random roller (not in the power train) at -40,30 (r=20).

Roller Radius Speed

1 (0,0) 10 10,000

2 (0,30) 20 -5,000

3 (32,54) 20 5,000


Sum of abs values: 20,000