网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
[USACO Open09]Tied Down
成绩 | 0 | 开启时间 | 2013年02月21日 星期四 23:02 |
折扣 | 0.8 | 折扣时间 | 2013年02月28日 星期四 23:02 |
允许迟交 | 是 | 关闭时间 | 2013年02月28日 星期四 23:02 |
输入文件 | tied.in | 输出文件 | tied.out |
Here is an example of the scene, viewed from above:
To help Bessie escape, the rest of the cows have stolen a saw from the barn. Please determine the minimum number of fence posts they must cut through and remove in order for Bessie to be able to pull free (meaning she can run away to the right without the rope catching on any of the fence posts). All (x,y) coordinates in the input (fence posts, Bessie, and line segment endpoints) lie in the range 0..10,000. All fence posts have the same x coordinate, and bx is larger than this value. PROBLEM NAME: tied INPUT FORMAT: * Line 1: Four space-separated integers: N, M, bx, by. * Lines 2..1+N: Line i+1 contains the space-separated x and y coordinates of fence post i. * Lines 2+N..2+N+M: Each of these M+1 lines contains, in sequence, the space-separated x and y coordinates of a point along the rope. The first and last points are always the same as Bessie's location (bx, by). SAMPLE INPUT (file tied.in): 2 10 6 1 2 3 2 1 6 1 2 4 1 1 2 0 3 1 1 3 5 4 3 0 0 1 3 2 6 1 INPUT DETAILS: There are two posts at (2,3) and (2,1). Bessie is at (6,1). The rope goes from (6,1) to (2,4) to (1,1), and so on, ending finally at (6,1). The shape of the rope is the same as in the figure above. OUTPUT FORMAT: * Line 1: The minimum number of posts that need to be removed in order for Bessie to escape by running to the right. SAMPLE OUTPUT (file tied.out): 1 OUTPUT DETAILS: Removing either post 1 or post 2 will allow Bessie to escape.
barn. Please determine the minimum number of fence posts they must cut through and remove in order for Bessie to be able to pull free (meaning she can run away to the right without the rope catching on any of the fence posts). All (x,y) coordinates in the input (fence posts, Bessie, and line segment endpoints) lie in the range 0..10,000. All fence posts have the same x coordinate, and bx is larger than this value. PROBLEM NAME: tied INPUT FORMAT: * Line 1: Four space-separated integers: N, M, bx, by. * Lines 2..1+N: Line i+1 contains the space-separated x and y coordinates of fence post i. * Lines 2+N..2+N+M: Each of these M+1 lines contains, in sequence, the space-separated x and y coordinates of a point along the rope. The first and last points are always the same as Bessie's location (bx, by). SAMPLE INPUT (file tied.in): 2 10 6 1 2 3 2 1 6 1 2 4 1 1 2 0 3 1 1 3 5 4 3 0 0 1 3 2 6 1 INPUT DETAILS: There are two posts at (2,3) and (2,1). Bessie is at (6,1). The rope goes from (6,1) to (2,4) to (1,1), and so on, ending finally at (6,1). The shape of the rope is the same as in the figure above. OUTPUT FORMAT: * Line 1: The minimum number of posts that need to be removed in order for Bessie to escape by running to the right. SAMPLE OUTPUT (file tied.out): 1 OUTPUT DETAILS: Removing either post 1 or post 2 will allow Bessie to escape.