凸包
在平面上能包含所有给定点的最小凸多边形叫做凸包，凸包用最小的周长围住了给定的所有点
凸包的解法
九茶巨巨九茶巨巨在这篇博客里面讲的非常清楚
我比较喜欢用的是扫描法，找到y轴最下面的点，然后作为基点使用极角排序。
排序过后根据叉积判断就好，时间复杂度就是排序的复杂度。
代码示例
圈奶牛
时间复杂度O(nlogn)1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
using namespace std;
const double eps = 1e-8;
const int N = 1e4+10;
int syn(double x)
{
if(fabs(x)<eps)return 0;
if(x>0)return 1;
else return -1;
}
struct Point{
double x,y;
}p[N],s[N];
stack<Point>st;
stack<Point>res;
Vector operator - (Point a,Point b){return {b.x-a.x,b.y-a.y};}
double Cross(Vector a,Vector b){return a.x*b.y-a.y*b.x;}
double dis(Point a,Point b){return sqrt((b.x-a.x)*(b.x-a.x)+(b.y-a.y)*(b.y-a.y));}
bool cmp(Point p1,Point p2)
{
double tmp=(Cross(p[0]-p1,p[0]-p2));
if(tmp>0)return 1;
if(tmp==0&&(dis(p1,p[0])>dis(p2,p[0])))return true;
}
int main()
{
int n;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%lf %lf",&p[i].x,&p[i].y);
if(i!=0&&p[i].y<p[0].y)
{
swap(p[i],p[0]);
}
}
sort(p+1,p+n,cmp);
double ans = 0;
int tot = 0;
s[0]=p[0];
for(int i=1;i<n;i++)
{
while(tot>0&&Cross(s[tot]-s[tot-1],p[i]-s[tot])<=0)tot--;
tot++;
s[tot]=p[i];
}
s[tot+1]=p[0];
for(int i=0;i<=tot;i++)
ans+=dis(s[i],s[i+1]);
printf("%.2lf\n",ans);
}
三维凸包
PS：做法留坑，先留下代码1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
using namespace std;
const int N=2010;
const double eps=1e-9;
int n,cnt,vis[N][N];
double ans;
double Rand() {return rand()/(double)RAND_MAX;}
double reps() {return (Rand()-0.5)*eps;}
struct Node
{
double x,y,z;
void shake() {x+=reps();y+=reps();z+=reps();}
double len() {return sqrt(x*x+y*y+z*z);}
Node operator - (Node A) {return (Node){x-A.x,y-A.y,z-A.z};}
Node operator * (Node A) {return (Node){y*A.z-z*A.y,z*A.x-x*A.z,x*A.y-y*A.x};}
double operator & (Node A) {return x*A.x+y*A.y+z*A.z;}
}A[N];
struct Face
{
int v[3];
Node Normal() {return (A[v[1]]-A[v[0]])*(A[v[2]]-A[v[0]]);}
double area() {return Normal().len()/2.0;}
}f[N],C[N];
int see(Face a,Node b) {return ((b-A[a.v[0]])&a.Normal())>0;}
void Convex_3D()
{
f[++cnt]=(Face){1,2,3};
f[++cnt]=(Face){3,2,1};
for(int i=4,cc=0;i<=n;i++)
{
for(int j=1,v;j<=cnt;j++)
{
if(!(v=see(f[j],A[i]))) C[++cc]=f[j];
for(int k=0;k<3;k++) vis[f[j].v[k]][f[j].v[(k+1)%3]]=v;
}
for(int j=1;j<=cnt;j++)
for(int k=0;k<3;k++)
{
int x=f[j].v[k],y=f[j].v[(k+1)%3];
if(vis[x][y]&&!vis[y][x]) C[++cc]=(Face){x,y,i};
}
for(int j=1;j<=cc;j++) f[j]=C[j];
cnt=cc;cc=0;
}
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>A[i].x>>A[i].y>>A[i].z,A[i].shake();
Convex_3D();
for(int i=1;i<=cnt;i++) ans+=f[i].area();
printf("%.3f\n",ans);
}