当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

1070:Deformed Wheel

题目描述
The village's carpentry is located by a hill side. The carpenter's two little boys play with a piece of wood which looks like a deformed wheel with two identical convex polygon-shaped faces. One boy sets the wooden wheel on a slope at the hill top and let it roll down. The other boy is to quickly place himself at where he guesses the rolling wood would stop. Your program is to help him make the right guess.

More formally, we consider the wooden wheel as a simple convex polygon and we approximate the hill by a sequence of connected line segments with decreasing slopes. The slope of the last segment in the sequence is assumed to be zero, and the slope of the first segment is assumed to be a positive number. Initially, the wheel is placed on the hill such that there is at least one point of contact between the wheel and segments. For example in the following figure, the wheel in its initial position is drawn in solid lines, while the final position is drawn in dashed lines.

At any instant, the wheel rotates around one of its vertices, say P, if the y-coordinate of its center of gravity is decreased (note that this condition is necessary at any instant during the motion). It can be easily shown that at any instant, there is at most one such vertex. Rotation around P is stopped when the wheel touches a segment. The motion continues until no vertex can be found such that the wheel can rotate around it. At any instant, assume that changing the position of the center of gravity in any direction for at most 10-5 units, does not affect the stability of the wheel. Also assume that the friction between the wheel and the surface of the hill is so high that the wheel never slides on the surface.
输入解释
The first line of the input contains a single integer t (1 <= t <= 10), the number of test cases, followed by the input data for each test case. In the first line of each test case there is an integer n (1 <= n <= 10), that indicates the number of the wheel vertices. In each of the next n lines, there is a pair of numbers which are x and y coordinates of the initial position of a vertex. After this, there is a single line containing the initial x and y coordinates of the center of gravity of the wheel. You can assume that the center of gravity is inside or on the boundary of the polygon (note that the given center of gravity is not necessarily computable from wheel's geometric shape). Next lines of the test data will describe the shape of the hill. The surface of the hill is approximated with a series of line segments with decreasing slopes ending with a horizontal line segment. For each segment, there is a line containing length and slope of a segment (both of them are real numbers). The lines are ordered in decreasing slope (The last line of this part of the input has slope zero). You can assume that the last (horizontal) line is long enough that the wheel would not pass its end. In the last line of the test case, there is a line containing the x and y coordinates of the right end-point of the first segment. All coordinates and slopes are real numbers.
输出解释
For each test case, there should be a single line in the output , containing two numbers which are x and y coordinates of the wheel's center of gravity. Round the numbers in the output to 3 digits after decimal point.
输入样例
1
4
40 30
30 37
24 30
30 26
27 29
30 1
100 0
40 30
输出样例
28.854 20.031

该题目是Virtual Judge题目,来自 北京大学POJ

题目来源 Tehran 2001

源链接: POJ-1070

最后修改于 2020-10-29T05:51:37+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
1000 10000