题解区的代码都是有问题的,没有考虑到一些细节问题,首先要防精度,排序的时候if(fabs(a.x-b.x)<eps) return a.y<b.y; 第二个是可能出现多点相对于极点共线的情况,你的排序函数第一按照角度排,第二还要按照到极点的距离从小到大排(记得输入的时候去重) 我的代码,仅供参考
#include<bits/stdc++.h>
#define int long long
#define eps 1e-6
#define N 100005
using namespace std;
struct Point{
double x,y;
Point(){}
Point(double x,double y):x(x),y(y){}
};//初始化一个点的结构体
typedef Point Vector;
Point a[N];
double p,q;
double cross(Vector A,Vector B){
return A.x*B.y-A.y*B.x;
}//叉积
double dot(Vector A,Vector B){
return A.x*B.x+A.y*B.y;
}//点积
double polygon_area(Point *p,int n){
double area=0;
for(int i=0;i<n;i++){
area+=cross(p[i],p[(i+1)%n]);
}
return area;
}//多边形面积
double dis(Point A,Point B){
return sqrt(1.0*(A.x-B.x)*(A.x-B.x)+1.0*(A.y-B.y)*(A.y-B.y));
}//点间距
bool cmp(Point a,Point b){
if(fabs(a.x-b.x)<eps) return a.y<b.y;
else return a.x<b.x;
}
bool cmp1(Point a,Point b){
double u=1.0*(a.x-p)*(a.x-p)+1.0*(a.y-q)*(a.y-q);
double v=1.0*(b.x-p)*(b.x-p)+1.0*(b.y-q)*(b.y-q);
if(a.y<q && b.y<q){
Point k={p,q};
if((a.x-p)*(a.x-p)*1.0/u==(b.x-p)*(b.x-p)*1.0/v){
return dis(a,k)<dis(b,k);
}
return (a.x-p)*(a.x-p)*1.0/u<(b.x-p)*(b.x-p)*1.0/v;
}
if(a.y>=q && b.y>=q){
Point k={p,q};
if((a.x-p)*(a.x-p)*1.0/u==(b.x-p)*(b.x-p)*1.0/v){
return dis(a,k)<dis(b,k);
}
return (a.x-p)*(a.x-p)*1.0/u>(b.x-p)*(b.x-p)*1.0/v;
}
return a.y<b.y;
}
double check(Vector A,Vector B){
return cross(A,B);
}
signed main(){
vector<pair<double,double>>v;
map<pair<double,double>,int>mp;
int n;cin>>n;
int g=0;
for(int i=0;i<n;i++){
double e,f;cin>>e>>f;
if(!mp[{e,f}]){
a[g].x=e;a[g].y=f;g++;mp[{e,f}]=1;
}
}
n=g;
sort(a,a+n,cmp);
p=a[0].x;q=a[0].y;
sort(a+1,a+n,cmp1);
for(int i=0;i<n;i++){
if(v.size()<2){
v.emplace_back(a[i].x,a[i].y);//不足2个就加入
}
else {
int lazy=0;
while(v.size()>1){//持续判断并删点,满足逆时针时停止,都不满足最后加上
Point l={v[v.size()-1].first-v[v.size()-2].first,v[v.size()-1].second-v[v.size()-2].second};
Point r={a[i].x-v[v.size()-2].first,a[i].y-v[v.size()-2].second};
if(check(l,r)<=0){
v.pop_back();
}
else {
v.emplace_back(a[i].x,a[i].y);lazy=1;break;
}
}
if(!lazy){//删完了之前的点,加上它
v.emplace_back(a[i].x,a[i].y);
}
}
}
double sum=0;
for(int i=0;i<v.size();i++){
Point l={v[i].first,v[i].second};
Point r={v[(i+1)%v.size()].first,v[(i+1)%v.size()].second};
sum+=dis(l,r);
}
printf("%.2lf",sum);
}