当时没有计算几何的基础,完全yy的解法,但是能过所有数据却过不了样例,有点怪,是样例其实是一种特殊情况吗(),那么这种东西要怎么改才能过阳历呢
#include <bits/stdc++.h>
// #define _int __int 128
using namespace std;
#define int long long
#define x first
#define y second
#define iter map<int,int>::iterator
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
namespace Mine{
mt19937_64 wql(1145141919810);
inline ll read(){
ll x=1,a=0;
char ch=getchar();
while(ch>'9' || ch<'0')x=(ch=='-')?-1:x,ch=getchar();
while(ch>='0' && ch<='9')
a=(a<<1)+(a<<3)+(ch-'0'),ch=getchar();
return a*x;
}
const int N=1e5+100;
int cmp(double ax,double ay,double bx,double by,double cx,double cy){
double tmp=(bx-ax)*(cy-by)-(by-ay)*(cx-bx);
if(tmp>0) return 1;
if(tmp<0) return -1;
return 0;
}
struct point{
double x,y;
}a[N];
int cmp(point a,point b,point c){
return cmp(a.x,a.y,b.x,b.y,c.x,c.y);
}
int n;
int up[N],tup,down[N],tdown;
double dist(point a,point b){
return sqrt(pow(a.x-b.x,2)+pow(a.y-b.y,2));
}
signed main(){
n=read();
for(int i=1;i<=n;i++) scanf("%lf %lf",&a[i].x,&a[i].y);
sort(a+1,a+1+n,[](point x,point y){return (x.x!=y.x)?x.x<y.x:x.y<y.y;});
double ans=0;
down[++tdown]=1;
for(int i=2;i<=n;i++){
// cout<<a[i].x<<" "<<a[i].y<<endl;
// if(fabs(a[down[tdown]].x-a[i].x)<1e-6){
// (a[down[tdown]].y>a[i].y) continue;
// down[++tdown]
// }
while(tdown>1 && cmp(a[down[tdown]],a[down[tdown-1]],a[i])>=0) tdown--;
down[++tdown]=i;
}
sort(a+1,a+1+n,[](point x,point y){return (x.x!=y.x)?x.x<y.x:x.y>y.y;});
up[++tup]=n;
for(int i=n-1;i>=1;i--){
// if(fabs(a[up[tup]].x-a[i].x)<1e-6){
// if(a[up[tup]].y<a[i].y) up[tup]=i;
// continue;
// }
while(tup>1 && cmp(a[up[tup]],a[up[tup-1]],a[i])>=0) tup--;
up[++tup]=i;
}
// for(int i=1;i<=tup;i++){
// cout<<a[up[i]].x<<" "<<a[up[i]].y<<endl;
// }
for(int i=2;i<=tup;i++){
// cout<<a[up[i]].y<<endl;
ans+=dist(a[up[i-1]],a[up[i]]);
}
for(int i=2;i<=tdown;i++){
ans+=dist(a[down[i-1]],a[down[i]]);
}
printf("%.2lf",ans);
return 0;
}
}
signed main(){
// freopen("wu.in","r",stdin);
// freopen("wu.out","w",stdout);
return Mine::main();
}