# 洛谷 P2742 [USACO5.1]圈奶牛Fencing the Cows /【模板】二维凸包

 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283 #include #include #include #include #include #include using namespace std; struct point {     double x, y;     long long id;     point() :x(0), y(0) {}     bool operator ==(const point& p) const {         return x == p.x && y == p.y;     } }PP; //PP: Polar Point vector points; double area2(point p, point q, point s) {     /*     |p.x p.y 1|     |q.x q.y 1| == 2*DirectedTriangleArea(p,q,s)     |s.x s.y 1|     */     return p.x * q.y - s.x * q.y         + q.x * s.y - q.x * p.y         + s.x * p.y - p.x * s.y; } bool toLeftTest(point p, point q, point s) {     //When return value large than 0, S is on the left side of ray PQ     return area2(p, q, s) > 0; } bool toLeftTest2(point p, point q, point s) {     //When return value large than 0, S is on the left side of ray PQ     return area2(p, q, s) >= 0; } bool cmp(const point& p1, const point& p2) { // Sort according to polar angle     return PP == p1 || !(PP == p2) && toLeftTest(PP, p1, p2); } point LTL(vector& points) { //Lowest then leftmost     point ltl = points[0];     for (int i = 1; i < points.size(); i++) {         if (points[i].y < ltl.y || points[i].y == ltl.y && points[i].x < ltl.x)             ltl = points[i];     }     return ltl; } vector grahamScan() {     PP = LTL(points);     sort(points.begin(), points.end(), cmp);     vector S, T;     S.push_back(points[0]); S.push_back(points[1]);     for (int i = points.size() - 1; i > 1; i--)T.push_back(points[i]);     while (!T.empty()) {         if (toLeftTest2(S[S.size() - 2], S[S.size() - 1], T[T.size() - 1])) {             S.push_back(T[T.size() - 1]);             T.pop_back();         }         else S.pop_back();     }     return S; } double dist(point x, point y) {     return sqrt((x.x - y.x) * (x.x - y.x) + (x.y - y.y) * (x.y - y.y)); } int main() {     ios::sync_with_stdio(false);     long long n;     cin >> n;     for (int i = 1; i <= n; i++) {         point tmp;         cin >> tmp.x >> tmp.y;         tmp.id = i;         points.push_back(tmp);     }     vector result;     if (points.size() > 2)result = grahamScan();     else result = points;     double res = 0;     for (int i = 0; i < result.size(); i++) {         res += dist(result[i % result.size()], result[(i + 1) % result.size()]);     }     cout.setf(ios::fixed);     cout << setprecision(2) << res; }