P2742 二维凸包模板 求凸包周长

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

const double eps = 1e-8;
const double dnf = 1e20;
const double pi = acos(-1.0);
const int maxp = 100010;
int sgn(double x){
	if(fabs(x) < eps) return 0;
	return x > 0 ? 1:-1;
}

struct Point{
	double x, y;
	Point(double x = 0, double y = 0):x(x),y(y){}
	
	Point operator + (const Point &b) const {
		return Point(x+b.x, y+b.y);
	}
	Point operator - (const Point &b) const {
		return Point(x-b.x, y-b.y);
	}
	Point operator * (const double &t) const {
		return Point(x*t, y*t);
	}
	Point operator / (const double &t) const {
		return Point(x/t, y/t);
	}
	double operator * (const Point &b) const {
		return x*b.x+y*b.y;
	}
	double operator ^ (const Point &b) const {
		return x*b.y-y*b.x;
	}
	bool operator == (const Point &b) const {
		return sgn(x-b.x)==0 && sgn(y-b.y) == 0; 
	} 

	bool operator < (const Point &b) const {
		if(sgn(x-b.x)!=0) return x < b.x;
		else return sgn(y-b.y)<0;
	}
	double dis(const Point &b){
		return hypot(x-b.x, y-b.y);
	}
};

struct polygon{
	int n;
	Point p[maxp];
	Line l[maxp];
	
	void add(Point q){
		p[n++] = q;//0~n-1
	}
	
	struct cmp{
		Point p;
		cmp(const Point &p0){
			p = p0;
		}
		bool operator()(const Point &aa, const Point &bb){
			Point a = aa, b = bb;
			int d = sgn((aa-p)^(bb-p));
			if(!d) return sgn(a.dis(p)-b.dis(p)) < 0;
			return d > 0;
		}
	};
	
	void norm(){
		Point mi = p[0];
		for(int i = 1; i < n; i++) mi = min(mi, p[i]);
		sort(p, p+n, cmp(mi));
	}
	
	void get_convex_graham(polygon &convex){
		norm();
		int &top = convex.n;
		top = 0;
		if(n == 1){
			top = 1;
			convex.p[0] = p[0];
			return;
		}
		if(n == 2){
			top = 2;
			convex.p[0] = p[0];
			convex.p[1] = p[1];
			if(convex.p[0] == convex.p[1]) top--;
			return ;
		}
		convex.p[0] = p[0];
		convex.p[1] = p[1];
		top = 2;
		for(int i = 2; i < n; i++){
			while(top > 1 && sgn((convex.p[top-1]-convex.p[top-2])^(p[i]-convex.p[top-2])) <= 0) top--;
			convex.p[top++] = p[i];
		}
		if(convex.n == 2 && (convex.p[0] == convex.p[1])) convex.n--;
	}
	
	double get_cir(){
		double sum = 0;
		for(int i = 0; i < n; i++){
			sum += p[i].dis(p[(i+1)%n]);
		}
		return sum;
	}
};

int main(){
	int n;
	cin >> n;
	polygon box, convex;
	for(int i = 1; i <= n; i++){
		double xx, yy;
		scanf("%lf%lf", &xx, &yy);
		box.add(Point(xx, yy));
	}
	box.get_convex_graham(convex);
	printf("%.2lf", convex.get_cir());
	return 0;
} 
上一篇:新手小白学习python第五周


下一篇:mysql 行转列,列转行