卡第一个测试点的原因
查看原帖
卡第一个测试点的原因
875221
killtzt7楼主2023/8/14 18:31

题解区的代码都是有问题的,没有考虑到一些细节问题,首先要防精度,排序的时候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);
}
2023/8/14 18:31
加载中...