[模板]二维凸包
aRenBigFather
2019-04-01 19:38:19
```cpp
#include <bits/stdc++.h>
using namespace std;
const int maxn = 10010;
struct Vec2{
double x,y;
Vec2(){}
Vec2(int _x,int _y){
x = _x;
y = _y;
}
inline Vec2 operator - (const Vec2 &a) const{
return Vec2(x-a.x,y-a.y);
}
inline double disTo(const Vec2 &b){
return sqrt((x-b.x)*(x-b.x)+(y-b.y)*(y-b.y));
}
inline double operator % (const Vec2 &a) const{
//xmul
return x*a.y - y*a.x;
}
inline bool operator < (const Vec2 &a) const{
if(x == a.x) return y < a.y;
return x < a.x;
}
}Points[maxn];
int n;
int sta[maxn],psta=0;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%lf%lf",&Points[i].x,&Points[i].y);
sort(Points+1,Points+1+n);
sta[++psta] = 1;
sta[++psta] = 2;
for(int i=3;i<=n;i++){
Vec2 pre = Points[sta[psta]] - Points[sta[psta-1]];
Vec2 now = Points[i] - Points[sta[psta]];
while(pre % now < 0.0){
if(psta == 1) break;
--psta;
pre = Points[sta[psta]] - Points[sta[psta-1]];
now = Points[i] - Points[sta[psta]];
}
sta[++psta] = i;
}
int mid = psta;
sta[++psta] = n;
sta[++psta] = n-1;
for(int i=n-2;i>=1;i--){
Vec2 pre = Points[sta[psta]] - Points[sta[psta-1]];
Vec2 now = Points[i] - Points[sta[psta]];
while(pre % now < 0.0){
if(psta == mid + 1) break;
--psta;
pre = Points[sta[psta]] - Points[sta[psta-1]];
now = Points[i] - Points[sta[psta]];
}
sta[++psta] = i;
}
double ans = 0;
for(int i=2;i<=psta;i++){
ans += Points[sta[i]].disTo(Points[sta[i-1]]);
}
printf("%.2f\n",ans);
return 0;
}
```