[USACO 2008 Mar S]The Loathesome Hay Baler
题号:NC24965
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 32 M,其他语言64 M
64bit IO Format: %lld

题目描述

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: Xi,Yi are the center of the roller (-5000 <= Xi <= 5000; -5000 <= Yi <= 5000); Ri is the roller's radius (3 <= Ri <= 800). The drive-roller is located at 0,0; the baler power take-off is located at Xt,Yt (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, Xt, and Yt
* Lines 2..N+1: Line i+1 describes roller i's properties: Xi, Yi, and Ri

输出描述:

* 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.
示例1

输入

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

输出

复制
20000

说明

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