if I say ...
先提供一个关于凸包的Andrew算法的小清新写法,之后我再想想你的代码(~~其实又来骗关~~)
```cpp
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#define int long long
using namespace std;
const int MAXN = 1e5+10;
const double eps = 1e-18;
const double PI = acos(-1);
struct point{
double x,y;
}pt[MAXN];
int n;
double a,b,r;
int stk[MAXN*10];
int siz;
double dot(point a,point b){
return a.x * b.x + a.y * b.y;
}
double cross(point a,point b){
return a.x * b.y - a.y * b.x;
}
double dis(point a,point b){
return sqrt( (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y) );
}
bool cmp(point a,point b){
if(a.x == b.x)return a.y < b.y;
return a.x < b.x;
}
point min(point a,point b){
return (point){ (a.x-b.x),(a.y-b.y) };
}
signed main(){
cin >> n;
int cnt = 0;
for(int i = 1;i <= n;i++){
cin >> pt[i].x >> pt[i].y;
}
sort(pt+1,pt+1+n,cmp);
siz = 0;
for(int i = 1;i <= n;i++){
while(siz > 1 && cross( min(pt[stk[siz]] , pt[stk[siz-1]]) , min(pt[stk[siz]] , pt[i]) ) <= 0 )siz--;
stk[++siz] = i;
}
int tmp = siz;
for(int i = n-1;i >= 1;i--){
while(siz > tmp && cross( min(pt[stk[siz]] , pt[stk[siz-1]]) , min(pt[stk[siz]] , pt[i]) ) <= 0 )siz--;
stk[++siz] = i;
}
double ans = 0;
for(int i = 1;i < siz;i++){
ans += dis(pt[stk[i]],pt[stk[i+1]]);
}
printf("%.2lf",ans);
}
```
by 帝都_henry26268 @ 2023-10-04 11:35:12
先给你个建议,把类似求距离,叉乘之类东西包装一下求值,另外就是变量命名不要使用p0,p1,p2这类,不然我实在看不懂。。。
by 帝都_henry26268 @ 2023-10-04 11:48:23
你这个在线处理太抽象了,最好离线下来用栈式结构把凸包求出来之后再计算距离
by 帝都_henry26268 @ 2023-10-04 11:49:51
@[帝都_henry26268](/user/315655) 在线处理个人感觉还行吧:(
```cpp
#include<bits/stdc++.h>
using namespace std;
int n=0;
double ans=0;
struct point {
double x;
double y;
}a[100001],m;
bool b[100001]={0};
double dis(int x1,int y1,int x2,int y2){
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
double cross(int x1,int y1,int x2,int y2){
return x1*y2-y1*x2;
}
int main() {
cin>>n;
for(int i=0; i<n; i++) {
cin>>a[i].x>>a[i].y;
m.x=min(m.x,a[i].x);
m.y=min(m.y,a[i].y);
}
int lastpoint=-1,point1=-1,firstpoint=-1;
for(int i=0; i<n; i++) {
point1=-1;
for(int j=0; j<n; j++) {
if(j!=lastpoint&&(b[j]==0||j==firstpoint)) {
if(lastpoint==-1) {
if(point1==-1) {
point1=j;
} else {
if(cross(a[point1].x+m.x,a[point1].y+m.y,a[j].x+m.x,a[j].y+m.y)>=0) {
point1=j;
}
}
} else {
if(point1==-1) {
point1=j;
} else {
if(cross(a[point1].x-a[lastpoint].x,a[point1].y-a[lastpoint].y,a[j].x-a[lastpoint].x,a[j].y-a[lastpoint].y)>=0) {
point1=j;
}
}
}
}
}
if(lastpoint==-1)firstpoint=point1;
else {
ans+=dis(a[lastpoint].x,a[lastpoint].y,a[point1].x,a[point1].y);
if(firstpoint==point1)break;
}
lastpoint=point1;
b[point1]=1;
}
printf("%.2lf",ans);
return 0;
}
```
by absolute_value @ 2023-10-04 17:48:10