记录编号	566100	评测结果	AAAAAAAA
题目名称	圈奶牛	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	0.041 s
提交时间	2021-11-01 15:49:32	内存使用	2.95 MiB

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>

struct Point_2 {
	double _x, _y;
	Point_2(double __x, double __y) {
		_x = __x, _y = __y;
	}

	double &x() {return _x;} 
	double &y() {return _y;}
	const double &x() const { return _x; }
	const double &y() const { return _y; }
};

double crossMul(const Point_2& base, const Point_2 &a, const Point_2 &b) {
	return (a.x() - base.x()) * (b.y() -  base.y()) - (b.x() - base.x()) * (a.y() - base.y());
}

	//只在BuildingVector.cpp中被用到
    template<class _Iterator, class T>
    static void convex_hull_2(_Iterator first, _Iterator last, std::back_insert_iterator<T> ins) {
        //Graham算法
       // auto minY = std::numeric_limits<CG_FLOAT_T>::max();
        if(last - first < 3) {
            throw std::logic_error("Can not get convex hull of a vertices set which has less 3 points.");
        }
        Point_2 *minYP = nullptr;
        for(auto p = first; p != last; p++) {
            if(!minYP) {
                minYP = &(*p);
            } else if(p->y() < minYP->y()) {
                minYP = &(*p);
            } else if(p->y() == minYP->y() && p->x() < minYP->x()) {
                minYP = &(*p);
            }
        }
        std::vector<Point_2> pts;
        for(auto p = first; p != last; p++) {
            if(&(*p) != minYP) {
                pts.push_back(*p);
            }
        }
        std::sort(pts.begin(), pts.end(), [&](const Point_2 &pa, const Point_2 &pb) {
            
            //auto c = crossMul(*minYP, pa, pb);
            //if(c > CG_EPS) return true;
            //if(fabs(c) <= CG_EPS && (pa - (*minYP)).squareLength() <= (pb - (*minYP)).squareLength()) {
            //    return true;
            //} return false;
            auto ang1 = atan2(pa.y() - minYP->y(), pa.x() - minYP->x());
            auto ang2 = atan2(pb.y() - minYP->y(), pb.x() - minYP->x());
            if(ang1 != ang2) 
                return ang1 < ang2;
            else return pa.x() < pb.x();
            //return ang1 < ang2 || (fabs(ang1 - ang2) < CG_EPS && (pa-(*minYP)).squareLength() < (pb-(*minYP)).squareLength()); 
        });
        std::vector<Point_2> stk;
        stk.push_back(*minYP);
        stk.push_back(pts[0]);
        for(int i = 1; i < pts.size(); i++) {
            while(stk.size() >= 2 && crossMul(stk[stk.size() - 2], stk[stk.size() - 1], pts[i]) < 0) {
                stk.pop_back();
            }
            stk.push_back(pts[i]);
        }
        //*(ins++) = *minYP;
        for(auto p = stk.begin(); p != stk.end(); p++) {
            *(ins++) = *p; 
        }
    }
int main() {
    freopen("fc.in", "r", stdin);
    freopen("fc.out", "w", stdout);
	int n;
	std::cin >> n;;
	std::vector<Point_2> pts;
	for(int i = 0; i < n; i++) {
		double x, y;
		std::cin >> x >> y;
		pts.push_back(Point_2(x, y));
	}
	std::vector<Point_2> res;
	convex_hull_2(pts.begin(), pts.end(), std::back_inserter(res));
	double len = 0;
	for(int i = 1; i < res.size(); i++) {
		auto xx = res[i].x() - res[i-1].x();
		auto yy = res[i].y() - res[i-1].y();
		len += sqrt(xx*xx+yy*yy);
	}
	auto xx = res.back().x() - res[0].x();
	auto yy = res.back().y() - res[0].y();
	len += sqrt(xx*xx+yy*yy);
	printf("%.2lf\n", len);
	return 0;
}