计算几何模板

慢慢填

#include <cmath>
#include <ctime>
#include <cstdio>
#include <vector>
#include <algorithm>
#define LL long long
#define Vector Point
#define Vec std::vector
#define sqr(x) ((x) * (x))

const double eps = 1e-10, pi = acos(-1);

inline int Sgn(double x) {
	return x < -eps ? -1 : x > eps;
}

struct Point {
	double x, y;
	Point() {}
	Point(double _x, double _y) : x(_x), y(_y) {}
	inline void input() {
		scanf("%lf%lf", &x, &y);
	}
	inline void output() {
		printf("%.2lf %.2lf\n", x, y);
	}
	inline friend bool operator ==(const Point &a, const Point &b) {
		return Sgn(a.x - b.x) == 0 && Sgn(a.y - b.y) == 0;
	}
	inline friend bool operator !=(const Point &a, const Point &b) {
		return a == b ? 0 : 1;
	}
	inline friend bool operator <(const Point &a, const Point &b) {
		return Sgn(a.x - b.x) < 0 || Sgn(a.x - b.x) == 0 && Sgn(a.y - b.y) < 0;
	}
	inline friend Vector operator +(const Vector &a, const Vector &b) {
		return Vector(a.x + b.x, a.y + b.y);
	}
	inline friend Vector operator -(const Vector &a, const Vector &b) {
		return Vector(a.x - b.x, a.y - b.y);
	}
	inline friend double operator *(const Vector &a, const Vector &b) {
		return a.x * b.y - a.y * b.x;
	}
	inline friend Vector operator *(const Vector &a, double t) {
		return Vector(a.x * t, a.y * t);
	}
	inline friend Vector operator /(const Vector &a, double t) {
		return Vector(a.x / t, a.y / t);
	}
	inline friend double dot(const Point &a, const Point &b) {
		return a.x * b.x + a.y * b.y;
	}
	inline friend double dis(const Point &a, const Point &b) {
		return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y));
	}
	inline friend double dis2(const Point &a, const Point &b) {
		return sqr(a.x - b.x) + sqr(a.y - b.y);
	}
	inline double len() {
		return sqrt(sqr(x) + sqr(y));
	}
	inline double len2() {
		return sqr(x) + sqr(y);
	}
	// 逆时针转 theta 度
	inline Vector rotate(double the) {
		double Sin = sin(the), Cos = cos(the);
		return Vector(x * Cos - y * Sin, x * Sin + y * Cos);
	}
	// b 绕 a 逆时针转 theta 度
	inline friend Point rotate(const Point &a, const Point &b, double the) {
		Vector tmp = (b - a).rotate(the);
		return a + tmp;
	}
    inline Vector Left() {
        return Vector(-y, x);
    }
    inline Vector Right() {
        return Vector(y, -x);
    }
	// 四边形
	inline friend double _Area(const Vector &a, const Vector &b) {
		return fabs(a * b);
	}
	// 三角形
	inline friend double Area(const Vector &a, const Vector &b, const Vector &c) {
		return _Area(a - c, b - c) / 2;
	}
	// 分点: ACB共线, |AC| : |CB| = l1 : l2, 则C = (A * l2 + B * l1) / (l1 + l2)
	inline friend Point Div(const Point &a, const Point &b, double l1, double l2) {
		return ((a * l2 + b * l1) / (l1 + l2));
	}
	inline friend Point Mid(const Point &a, const Point &b) {
		return Div(a, b, 1.0, 1.0);
	}
};

struct Line {
	Point a, b;
	Line() {}
	// 两点式
	Line(Point _a, Point _b) : a(_a), b(_b) {}
	// 点斜式
	Line(Point p, double angle) {
		a = p;
		if (Sgn(angle - pi / 2) == 0) a + Point(0, 1);
		else a + Point(1, tan(angle));
	}
	// 一般式
	Line(double _a, double _b, double _c) {
		if (Sgn(_a) == 0) {
			a = Point(0, -_c / _b);
			b = Point(1, -_c / _b);
		} else if (Sgn(_b) == 0) {
			a = Point(-_c / _a, 0);
			b = Point(-_c / _b, 1);
		} else {
			a = Point(0, -_c / _b);
			b = Point(1, (-_a - _c) / _b);
		}
	}
	inline void input() {
		a.input(), b.input();
	}
	// 线段长
	inline double length() {
		return dis(a, b);
	}
	inline double angle() {
		double the = atan2(b.y - a.y, b.x - a.x);
		if (Sgn(the) < 0) the += pi;
		if (Sgn(the - pi) == 0) the -= pi;
		return the;
	}
	inline bool PointonLine(Point p) {
		return Sgn((p - a) * (b - a)) == 0;
	}
	inline bool PointonSeg(Point p) {
		return PointonLine(p) && Sgn(dot(p - a, p - b)) <= 0;
	}
	// 平行
	inline friend bool Parallal(const Line &x, const Line &y) {
		return Sgn((x.b - x.a) * (y.b - y.a)) == 0;
	}
	// 垂直
	inline friend bool Vertical(const Line &x, const Line &y) {
		return Sgn(dot(x.b - x.a, y.b - y.a)) == 0;
	}
	// 点到直线距离
	inline double disLine(const Point &p) {
		return fabs((p - a) * (b - a)) / length();
	}
	// 点到线段距离
	inline double disSeg(const Point &p) {
		if (Sgn(dot(p - a, b - a)) < 0 || Sgn(dot(p - b, a - b)) < 0)
			return std::min(dis(a, p), dis(b, p));
		return disLine(p);
	}
	/* 0:平行 1:在逆时针 2:在顺时针*/
	inline int relation(const Point &p) {
		int c = Sgn((p - a) * (b - a));
		if (c > 0) return 2;
		else if (c == 0) return 0;
		else return 1;
	}
	// 直线交点: 根据有向面积比算出|AO|:|OB|, 使用分点计算O
	// 注意A与B叉积计算顺序相反
	inline friend Point Inter(const Line &x, const Line &y) {
		return Div(x.a, x.b, (y.b - x.a) * (y.a - x.a), (y.a - x.b) * (y.b - x.b));
	}
};

struct Circle {
	Point p;
	double r;
	Circle() {}
	Circle(Point _p, double _r) : p(_p), r(_r) {}
	Circle(double _x, double _y, double _r) : p(Point(_x, _y)), r(_r) {}
	Circle(const Point &a, const Point &b, const Point &c) {
        Point M1 = Mid(a, b), M2 = Mid(a, c);
        p = Inter(Line(M1, M1 + (M1 - a).Left()), Line(M2, M2 + (M2 - a).Left()));
        r = dis(p, a);
	}
	inline void input() {
		p.input(), scanf("%lf", &r);
	}
	/* 0:相离  1:相交  2:a内含于b */
	inline friend int relationCircle(const Circle &a, const Circle &b) {
		double d = dis(a.p, b.p);
		if (Sgn(a.r + b.r - d) < 0) return 0;
		double l = b.r - a.r;
		if (Sgn(l - d) >= 0) return 2;
		return 1;
	}
	/* 0:在圆外  1:在圆上  2:在圆内 */
	inline int relationPoint(const Point &a) {
		double d = dis(p, a);
		int c = Sgn(d - r);
		if (c > 0) return 0;
		else if (c == 0) return 1;
		else return 2;
	}
};

struct Polygon {
	int n;
	Vec<Point> p;
	Vec<Line> l;
	inline void input() {
		scanf("%d", &n), p.resize(n);
		for (int i = 0; i < n; ++i) p[i].input();
	}
	inline void Get_Line() {
		for (int i = 0; i < n; ++i) l.push_back(Line(p[i], p[(i + 1) % n]));
	}
	// 周长
	inline double Circ() {
		double res = 0;
		for (int i = 0; i < n; ++i) res += dis(p[i], p[(i + 1) % n]);
		return res;
	}
	// 面积
	inline double Area() {
		double res = 0;
		for (int i = 0; i < n; ++i) res += _Area(p[i], p[(i + 1) % n]);
		return res / 2;
	}
	// 极角序
	struct cmp_pol {
		Point p;
		cmp_pol(const Point &_p) {
			p = _p;
		}
		inline bool operator() (const Point &a, const Point &b) {
			int d = Sgn((a - p) * (b - p));
			return d != 0 ? d > 0 : Sgn(dis(p, a) - dis(p, b)) < 0;
		}
	};
	// 凸包
	inline void GetConvex(Polygon &Con) {
		std::sort(p.begin(), p.end());
		Con.n = n, Con.p.resize(n << 1);
		for (int i = 0; i < std::min(n, 2); ++i) Con.p[i] = p[i];
		if (n <= 2) return;
		int &top = Con.n = 1;// 为了排除左端点相同, top表示的是 (总点数-1)
		for (int i = 2; i < n; ++i) {
			while (top && Sgn((p[i] - Con.p[top]) * (Con.p[top] - Con.p[top - 1])) >= 0) --top;
			Con.p[++top] = p[i];
		}
		int tmp = top;
		Con.p[++top] = p[n - 2];// 为了排除右端点相同, 第二次扫描开始前只要加倒数第二个点进去
		for (int i = n - 3; ~i; --i) {
			while (top != tmp && Sgn((p[i] - Con.p[top]) * (Con.p[top] - Con.p[top - 1])) >= 0) --top;
			Con.p[++top] = p[i];
		}
	}
	/* 0: 点上  1:边上  2:内部  3:外部 */
	inline int relationPoint(const Point q) {}
	// 最小圆覆盖
	inline Circle MinCircleCover() {
		srand(time(NULL));
		std::random_shuffle(p.begin(), p.end());
		Circle res = Circle(p[0], 0);
		for (int i = 1; i < n; ++i)
			if (res.relationPoint(p[i]) == 0) {
				res = Circle(p[i], 0);
				for (int j = 0; j < i; ++j)
					if (res.relationPoint(p[j]) == 0) {
						res.p = Mid(p[i], p[j]);
                        res.r = dis(res.p, p[j]);
						for (int k = 0; k < j; ++k)
							if (res.relationPoint(p[k]) == 0)
                                res = Circle(p[i], p[j], p[k]);
					}
			}
        return res;
	}
	// 旋转卡壳求凸多边形直径
	inline double Diameter() {
		if (n == 2) return dis2(p[0], p[1]);
		int q = 0;
		double res = 0;
		for (int i = 0; i < n; ++i) {
			while (Sgn(l[i].disLine(p[q]) - l[i].disLine(p[(q + 1) % n])) <= 0) q = (q + 1) % n;
			res = std::max(res, std::max(dis2(p[i], p[q]), dis2(p[(i + 1) % n], p[q])));
		}
		return res;
	}
};

Polygon G, Con;

int main() {
	// freopen("1.in", "r", stdin);
	// freopen("1.out", "w", stdout);
	G.input();
	G.GetConvex(Con);
	printf("%.2lf\n", Con.Circ());
	return 0;
}