#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; static const double EPS = 1e-8; static const double PI = 4.0 * atan(1.0); static const double PI2 = 8.0 * atan(1.0); typedef long long ll; typedef unsigned long long ull; #define ALL(c) (c).begin(), (c).end() #define CLEAR(v) memset(v,0,sizeof(v)) #define MP(a,b) make_pair((a),(b)) #define REP(i,n) for(int i=0;i<(int)n;++i) #define ABS(a) ((a)>0?(a):-(a)) template T MIN(const T& a, const T& b) { return a < b ? a : b; } template T MAX(const T& a, const T& b) { return a > b ? a : b; } template void MIN_UPDATE(T& a, const T& b) { if (a > b) a = b; } template void MAX_UPDATE(T& a, const T& b) { if (a < b) a = b; } // 以下コピペ typedef complex P; struct L : public vector

{ L(const P &a, const P &b) { push_back(a); push_back(b); } }; bool intersectSP(const L &s, const P &p) { return abs(s[0]-p)+abs(s[1]-p)-abs(s[1]-s[0]) < EPS; // triangle inequality } // 以下ライブラリ void fillTiming(const vector

& domino, vector& timings, double v) { timings.push_back(0.0); for (int i = 1; i < domino.size(); ++i) { timings.push_back(timings.back() + abs(domino[i] - domino[i - 1]) / v); } } P timingToPos(const vector

& domino, const vector& timings, double timing) { assert(domino.size() == timings.size()); if (timings.back() < timing + EPS) { return domino.back(); } if (timing < EPS) { return domino.front(); } // 整数用二分探索 int L = 0; int R = domino.size(); while (L + 1 < R){ ll M = (L + R) / 2; if (timings[M] < timing){ L = M; } else { R = M; } } return (domino[L] * (timings[L + 1] - timing) + domino[L + 1] * (timing - timings[L])) / (timings[L + 1] - timings[L]); } double calculateMeetingTiming(const vector

& domino, const vector& timings, double startTiming, const P& myPos, double myV) { double l = startTiming; double r = 1e10; REP(loop, 200) { double m = (l + r) * 0.5; if (abs(timingToPos(domino, timings, m) - myPos ) < myV * (m - startTiming)) { r = m; } else { l = m; } } return l; } double posToTiming(const vector

& domino, const vector& timings, const P& pos) { for (int i = 0; i < domino.size() - 1; ++i) { if (!intersectSP(L(domino[i], domino[i + 1]), pos)) { continue; } return (timings[i] * abs(domino[i + 1] - pos) + timings[i + 1] * abs(domino[i] - pos)) / abs(domino[i] - domino[i + 1]); } assert(false); } // 順方向に進んだ後、停止する場合 double solveForwardOnly(const vector

& domino, const vector& timings, const P& collapsePos, const P& myPos, double myV) { double startTiming = posToTiming(domino, timings, collapsePos); double meetingTiming = calculateMeetingTiming(domino, timings, startTiming, myPos, myV); // 逆方向が端点に付くタイミング、又は順方向に到達したタイミング return max(startTiming, meetingTiming - startTiming); } double solveForwardAndBackward(const vector

& dominoForward, const vector& timingsForward, const vector

& dominoBackward, const vector& timingsBackward, const P& collapsePos, const P& myPos, double myV) { double firstStartTimingForward = posToTiming(dominoForward, timingsForward, collapsePos); double firstMeetingTimingForward = calculateMeetingTiming(dominoForward, timingsForward, firstStartTimingForward, myPos, myV); P firstMeetingPos = timingToPos(dominoForward, timingsForward, firstMeetingTimingForward); double secondStatTimingBackward = posToTiming(dominoBackward, timingsBackward, collapsePos) + firstMeetingTimingForward - firstStartTimingForward; double secondMeetingTimingBackward = calculateMeetingTiming(dominoBackward, timingsBackward, secondStatTimingBackward, firstMeetingPos, myV); return firstMeetingTimingForward - firstStartTimingForward + secondMeetingTimingBackward - secondStatTimingBackward; } double solveNoTouch(const vector

& domino, const vector& timings, const P& collapsePos) { double startTiming = posToTiming(domino, timings, collapsePos); return max(startTiming, timings.back() - startTiming); } double solve(const vector

& dominoForward, const vector& timingsForward, const vector

& dominoBackward, const vector& timingsBackward, const P& collapsePos, const P& myPos, double myV) { if (abs(collapsePos - myPos) < EPS) { return 0.0; } double result = solveForwardOnly(dominoForward, timingsForward, collapsePos, myPos, myV); result = min(result, solveForwardAndBackward(dominoForward, timingsForward, dominoBackward, timingsBackward, collapsePos, myPos, myV)); result = min(result, solveNoTouch(dominoForward, timingsForward, collapsePos)); return result; } // 以下ユニットテスト #define assertEquals(expected, actual) assert(abs((expected) - (actual)) < EPS) void testTimingToPos() { vector

domino; vector timings; REP(i, 100 + 1) { domino.push_back(i); timings.push_back(i); } assertEquals(0.0, timingToPos(domino, timings, -1.0)); assertEquals(20.0, timingToPos(domino, timings, 20.0)); assertEquals(30.2, timingToPos(domino, timings, 30.2)); assertEquals(100.0, timingToPos(domino, timings, 120.0)); } void testCalculateMeetingTiming() { vector

domino; vector timings; REP(i, 100 + 1) { domino.push_back(i); timings.push_back(i); } assertEquals(50.0, calculateMeetingTiming(domino, timings, 0.0, 100.0, 1.0)); assertEquals(50.0, calculateMeetingTiming(domino, timings, 10.0, 90.0, 1.0)); assertEquals(40.0, calculateMeetingTiming(domino, timings, 10.0, 100.0, 2.0)); } void testSolveForwardOnly() { vector

domino; vector timings; REP(i, 100 + 1) { domino.push_back(i); timings.push_back(i); } assertEquals(50.0, solveForwardOnly(domino, timings, 50.0, P(55.0, 10.0), 2.0)); assertEquals(5.0, solveForwardOnly(domino, timings, 1.0, P(6.0, 10.0), 2.0)); } void testSolveForwardAndBackward() { vector

dominoForward, dominoBackward; vector timingsForward, timingBackward; REP(i, 100 + 1) { dominoForward.push_back(i); dominoBackward.push_back(100 - i); timingsForward.push_back(i); timingBackward.push_back(i); } assertEquals(15.0, solveForwardAndBackward(dominoForward, timingsForward, dominoBackward, timingBackward, 50.0, P(55.0, 10.0), 2.0)); } void test() { testTimingToPos(); testCalculateMeetingTiming(); testSolveForwardOnly(); testSolveForwardAndBackward(); exit(0); } int main() { //test(); std::ios::sync_with_stdio(false); int N; cin >> N; vector

dominoForward; REP(n, N) { double x, y; cin >> x >> y; dominoForward.push_back(P(x, y)); } vector

dominoBackward = dominoForward; reverse(ALL(dominoBackward)); double collapseX, collapseY, dominoV; double myX, myY, myV; cin >> collapseX >> collapseY >> dominoV >> myX >> myY >> myV; P collapsePos(collapseX, collapseY); P myPos(myX, myY); vector timingsForward, timingsBackward; fillTiming(dominoForward, timingsForward, dominoV); fillTiming(dominoBackward, timingsBackward, dominoV); double answer = min(solve(dominoForward, timingsForward, dominoBackward, timingsBackward, collapsePos, myPos, myV), solve(dominoBackward, timingsBackward, dominoForward, timingsForward, collapsePos, myPos, myV)); printf("%.20f\n", answer); }