Graham算法
先对所有点极角排序，其实这里有一个比较骚的操作，不用比x，y，直接算两个点的叉积
然后根据叉积的定义就可以看出这个极角的大小啦！
然后我们找到最靠左的那个点，把它压入栈，每次判断下一个点j和当前点i的叉积是否<0
如果小于0，还是由叉积的定义，j与i的连线是向右拐的（形象理解一下），所以就可以把这个点压入栈
持续递归到回到原点，栈里的点就是凸包集合
#include#include #include #include #include #include using namespace std;#define O(x) cout << #x << " " << x << endl;#define O_(x) cout << #x << " " << x << " ";#define B cout << "breakpoint" << endl;typedef double db;inline int read(){ int ans = 0,op = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') op = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { (ans *= 10) += ch - '0'; ch = getchar(); } return ans * op;}const int maxn = 1e5 + 5;int n;struct point{ db x,y; void clear() { x = y = 0; } point operator - (const point &b) { point c; c.clear(); c.x = x - b.x,c.y = y - b.y; return c; } db operator * (const point &b) { return x * b.y - y * b.x; } db dis() { return x * x + y * y; }}p[maxn],st[maxn];db calc(point a,point b){ point c = a - b; return sqrt(c.dis()); }bool cmp(int a,int b){ db dta = (p[a] - p[1]) * (p[b] - p[1]); if(dta != 0) return dta > 0; return (p[a] - p[1]).dis() < (p[b] - p[1]).dis();}int top;void Graham(){ int id = 1; for(int i = 2;i <= n;i++) if(p[i].x < p[id].x || (p[i].x == p[id].x && p[i].y < p[id].y)) id = i; if(id != 1) swap(p[1],p[id]); int tp[maxn]; for(int i = 1;i <= n;i++) tp[i] = i; sort(tp + 2,tp + 1 + n,cmp); st[++top] = p[1]; for(int i = 2;i <= n;i++) { int j = tp[i]; while(top >= 2 && (p[j] - st[top - 1]) * (st[top] - st[top - 1]) >= 0) top--; st[++top] = p[j]; }}db ans;int main(){ n = read(); for(int i = 1;i <= n;i++) scanf("%lf%lf",&p[i].x,&p[i].y); Graham(); st[top + 1] = st[1]; for(int i = 2;i <= top + 1;i++) ans += calc(st[i],st[i - 1]); printf("%.2lf",ans);}