HBC233137[JSOI2013]旅行时的困惑,贪心Chris and Road题解

挑战自我，勇攀编程高峰！全网最全C++题库，助您成为编程达人。

And while Mishka is enjoying her trip... Chris is a little brown bear. No one knows, where and when he met Mishka, but for a long time they are together (excluding her current trip). However, best

And while Mishka is enjoying her trip... Chris is a little brown bear. No one knows, where and when he met Mishka, but for a long time they are together (excluding her current trip). However, best friends are important too. John is Chris' best friend. Once walking with his friend, John gave Chris the following problem: At the infinite horizontal road of width www, bounded by lines y = 0y = 0y = 0 and y = wy = wy = w, there is a bus moving, presented as a convex polygon of nnn vertices. The bus moves continuously with a constant speed of vvv in a straight OxOxOx line in direction of decreasing xxx coordinates, thus in time only x coordinatestextbf{only} x textbf{coordinates}only x coordinates of its points are changing. Formally, after time ttt each of xxx coordinates of its points will be decreased by vtvtvt. There is a pedestrian in the point (0, 0)(0, 0)(0, 0), who can move only by a vertical pedestrian crossing, presented as a segment connecting points (0, 0)(0, 0)(0, 0) and (0, w)(0, w)(0, w) with any speed not exceeding uuu. Thus the pedestrian can move only in a straight line OyOyOy in any direction with any speed not exceeding uuu and not leaving the road borders. The pedestrian can instantly change his speed, thus, for example, he can stop instantly. Please look at the sample note picture for better understanding. We consider the pedestrian is hit by the bus, if at any moment the point he is located in lies strictly insidetextbf{strictly inside}strictly inside the bus polygon (this means that if the point lies on the polygon vertex or on its edge, the pedestrian is not hit by the bus). You are given the bus position at the moment 000. Please help Chris determine minimum amount of time the pedestrian needs to cross the road and reach the point (0, w)(0, w)(0, w) and not to be hit by the bus.

全网最全C++题库，助您挑战自我，突破极限，成为编程领域的佼佼者！

标签： HBC233137[JSOI2013]旅行时的困惑 贪心Chris and Road题解