#include #include #include #include #include #include #include using namespace std; typedef long long int ll; #define x first #define y second ll vectorProduct(ll x1, ll y1, ll x2, ll y2) { return x1*y2 - x2*y1; } bool intersects(ll x1, ll y1, ll x2, ll y2, ll x3, ll y3, ll x4, ll y4) { ll p1 = vectorProduct(x3 - x1, y3 - y1, x2 - x1, y2 - y1); ll p2 = vectorProduct(x4 - x1, y4 - y1, x2 - x1, y2 - y1); if ((p1 < 0) && (p2 > 0) || (p2 < 0 && p1 > 0)){ p1 = vectorProduct(x1 - x3, y1 - y3, x4 - x3, y4 - y3); p2 = vectorProduct(x2 - x3, y2 - y3, x4 - x3, y4 - y3); if ((p1 < 0) && (p2 > 0) || (p2 < 0 && p1 > 0)) { return true; } return false; } return false; } bool intersects(const pair &p1, const pair &p2, const pair &p3, const pair &p4){ return intersects(p1.x, p1.y, p2.x, p2.y, p3.x, p3.y, p4.x, p4.y); } struct Vertex { vector> next; double distance = -1; }; int main() { int nclouds, sx, sy, tx, ty, c; cin >> nclouds >> sx >> sy >> tx >> ty; vector> allPoints; vector, pair>> allSegments; allPoints.push_back({sx, sy}); allPoints.push_back({tx, ty}); for (int i=0; i> c; vector> points(c); for (int j=0; j> points[j].x >> points[j].y; } sort(points.begin(), points.end()); vector> upper; upper.push_back(points[0]); for (int j=1; j= 2) { pair &prelast = upper[int(upper.size()) - 2]; if (vectorProduct(points[j].x - prelast.x, points[j].y - prelast.y, upper.back().x - prelast.x, upper.back().y - prelast.y) <= 0) { upper.pop_back(); } else { break; } } upper.push_back(points[j]); } vector> lower; lower.push_back(points[0]); for (int j=1; j= 2) { pair &prelast = lower[int(lower.size()) - 2]; if (vectorProduct(points[j].x - prelast.x, points[j].y - prelast.y, lower.back().x - prelast.x, lower.back().y - prelast.y) >= 0) { lower.pop_back(); } else { break; } } lower.push_back(points[j]); } for (int i=0; i graph(n); for (int i=0; i> pq; pq.push({0, 0}); while (!pq.empty()) { double d = -pq.top().first; int v = pq.top().second; pq.pop(); if (graph[v].distance != -1) { continue; } graph[v].distance = d; if (v == 1) { break; } for (auto& s: graph[v].next) { if (graph[s.first].distance == -1) { pq.push({-(d + s.second), s.first}); } } } cout << setprecision(9) << graph[1].distance << '\n'; return 0; }