凸包相关

#include<bits/stdc++.h>
#define int long long
#define DB double
#define N 1000100
using namespace std;
int n,top;
struct sb{DB x,y;}e[N],stk[N];
inline DB cross(sb a,sb b,sb c){return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);}
inline DB js(sb a,sb b){return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}
inline int cmp(sb a,sb b){if(a.x==b.x)return a.y<b.y;return a.x<b.x;}
inline DB Andrew()
{
	sort(e+1,e+n+1,cmp);
	for(int i=1;i<=n;i++)
	{
		while(top>1&&cross(stk[top-1],stk[top],e[i])<=0)top--;
		stk[++top]=e[i];
	}
	int t=top;
	for(int i=n-1;i>=1;i--)
	{
		while(top>t&&cross(stk[top-1],stk[top],e[i])<=0)top--;
		stk[++top]=e[i];
	}
	DB res=0;
	for(int i=1;i<top;i++)res+=js(stk[i],stk[i+1]);
	return res;
}
signed main()
{
	cin>>n;
	for(int i=1;i<=n;i++)cin>>e[i].x>>e[i].y;
	DB ans=Andrew();
	printf("%.2lf\n",ans);
	return 0;
}

#include<bits/stdc++.h>
#define int long long
#define DB double
#define N 1000100
using namespace std;
int t,n,top;char c;
struct sb{DB x,y;}e[N],stk[N];
inline DB cross(sb a,sb b,sb c){return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);}
inline DB js(sb a,sb b){return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}
inline int cmp(sb a,sb b){if(a.x==b.x)return a.y<b.y;return a.x<b.x;}
inline void Andrew()
{
	sort(e+1,e+n+1,cmp);
	for(int i=1;i<=n;i++)
	{
		while(top>1&&cross(stk[top-1],stk[top],e[i])<0)top--;
		stk[++top]=e[i];
	}
	int t=top;
	for(int i=n-1;i>=1;i--)
	{
		while(top>t&&cross(stk[top-1],stk[top],e[i])<0)top--;
		stk[++top]=e[i];
	}
}
signed main()
{
	cin>>t;
	while(t--)
	{
		top=0;
		cin>>n;
		for(int i=1;i<=n;i++)cin>>e[i].x>>e[i].y>>c;
		Andrew();
		cout<<top-1<<endl;
		for(int i=1;i<top;i++)cout<<(int)stk[i].x<<" "<<(int)stk[i].y<<endl;
	}
	return 0;
}