#include #include #include #include using namespace std; // Bod struct point { long long x, y; point(long long x=0, long long y=0) : x(x), y(y) {} }; // Operátor < na uspořádání bodů bool operator< (const point &A, const point &B) { return A.x < B.x || ( A.x == B.x && A.y < B.y ); } // Vektorový součin: vráti >0 / 0 / <0 podle toho, zda ZAB zatáčí // proti směru ručiček / jde rovně / zatáčí po směru long long cross(const point &Z, const point &A, const point &B) { return (A.x-Z.x) * (B.y-Z.y) - (A.y-Z.y) * (B.x-Z.x); } // Skalární součin: pro Z, A, B na přímce vrátí >0, jsou-li A a B na téže straně Z, // <0, pokud jsou na opačných stranách. long long dot(const point &Z, const point &A, const point &B) { return (A.x-Z.x) * (B.x-Z.x) + (A.y-Z.y) * (B.y-Z.y); } // Konvexní obal pomocí Grahamova algoritmu // Předpokládá, že P je setříděna zleva doprava. vector convex_hull(vector P) { int n = P.size(), k = 0; vector H(2*n); for (int i = 0; i < n; i++) { while (k >= 2 && cross(H[k-2], H[k-1], P[i]) <= 0) k--; H[k++] = P[i]; } for (int i = n-2, t = k+1; i >= 0; i--) { while (k >= t && cross(H[k-2], H[k-1], P[i]) <= 0) k--; H[k++] = P[i]; } H.resize(k-1); return H; } // Obvod mnohoúhelníka double circumference(const vector &P) { int N = P.size(); double answer = 0.; for (int n=0; n &P) { int N = P.size(); long long answer=0; for (int n=0; n> N; vector P(N); for (int n=0; n> P[n].x >> P[n].y; sort(P.begin(), P.end()); double answer = circumference(convex_hull(P)); for (int a=0; a P1, P2; for (int i=0; i 0) P2.push_back(P[i]); if (cp == 0) { if (dot(P[a],P[b],P[i]) < 0) P1.push_back(P[i]); else P2.push_back(P[i]); } } vector H1 = convex_hull(P1), H2 = convex_hull(P2); if (twice_area(H1) > 0 && twice_area(H2) > 0) answer = min( answer, circumference(H1) + circumference(H2) ); } cout << setprecision(15) << answer << endl; return 0; }