int sgn(double x){
if (x>eps)return 1;
if (x<-eps)return -1;
return 0;
}
struct vec{
double x,y;
vec(){x=y=0;}
vec(double _x,double _y){x=_x,y=_y;}
vec operator + (vec v){return vec(x+v.x,y+v.y);}
vec operator - (vec v){return vec(x-v.x,y-v.y);}
vec operator * (double v){return vec(x*v,y*v);}
vec operator / (double v){return vec(x/v,y/v);}
double operator * (vec v){return x*v.x+y*v.y;}
};
bool cmpXY(vec a,vec b){
if (sgn(a.x-b.x))return a.x<b.x;
return a.y<b.y;
}
double cross(vec a ,vec b){
return a.x*b.y-a.y*b.x;
}
int convec_hull(vec*v,int n,vec* z){// 输入 数据大小 答案
sort(v,v+n,cmpXY);
int m = 0;
for(int i=0;i<n;i++){
while (m>1 && cross(z[m-1]-z[m-2],v[i]-z[m-2])<=0)--m;
z[m++] = v[i];
}
int k = m;
for(int i=n - 2;i>=0;--i) {
while( m > k && cross(z[m-1]-z[m-2],v[i]-z[m-2]) <= 0 ) --m;
z[m++] = v[i];
}
if(n>1)--m;
return m;
}
板子题:
P2742
给n 个点,求形成的凸包的周长。
样例1
4
4 8
4 12
5 9.3
7 8
输出
12.00
#include<bits/stdc++.h>
using namespace std;
#define N 1000010
const int mod = 1000000007;
const int inf = 1000000007;
const double eps = 1e-9;
void in(int &x){
x=0;char c=getchar();
int y=1;
while(c<'0'||c>'9'){if(c=='-')y=-1;c=getchar();}
while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
x*=y;
}
void o(int x){
if(x<0){x=-x;putchar('-');}
if(x>9)o(x/10);
putchar(x%10+'0');
}
int sgn(double x){
if (x>eps)return 1;
if (x<-eps)return -1;
return 0;
}
struct vec{
double x,y;
vec(){x=y=0;}
vec(double _x,double _y){x=_x,y=_y;}
vec operator + (vec v){return vec(x+v.x,y+v.y);}
vec operator - (vec v){return vec(x-v.x,y-v.y);}
vec operator * (double v){return vec(x*v,y*v);}
vec operator / (double v){return vec(x/v,y/v);}
double operator * (vec v){return x*v.x+y*v.y;}
};
bool cmpXY(vec a,vec b){
if (sgn(a.x-b.x))return a.x<b.x;
return a.y<b.y;
}
double cross(vec a ,vec b){
return a.x*b.y-a.y*b.x;
}
int convec_hull(vec*v,int n,vec* z){
sort(v,v+n,cmpXY);
int m = 0;
for(int i=0;i<n;i++){
while (m>1 && cross(z[m-1]-z[m-2],v[i]-z[m-2])<=0)--m;
z[m++] = v[i];
}
int k = m;
for(int i=n - 2;i>=0;--i) {
while( m > k && cross(z[m-1]-z[m-2],v[i]-z[m-2]) <= 0 ) --m;
z[m++] = v[i];
}
if(n>1)--m;
return m;
}
double Length(vec x){
return sqrt(x.x*x.x+x.y*x.y);
}
int n;
vec a[N],ans[N];
signed main(){
in(n);
for(int i=0;i<n;i++){
cin>>a[i].x>>a[i].y;
}
int m=convec_hull(a,n,ans);
double ANS=0.0;
for(int i=0;i<m;i++){
ANS += Length(ans[i+1]-ans[i]);
}
printf("%.2lf\n",ANS);
return 0;
}