XCPC Notes

Appearance

发布时间：2025-05-29

前言 ​

记录XCPC出现的一些中等难度的计算几何

2024ICPC香港E ​

链接在这里插入图片描述 题意：

凹包题

定义凹包为所有的内角中恰好只有一个大于pipi的内角，并且包含所有给定的nn个点的集合

计算所有凹包的面积和2

思路：

首先计算出nn个点的凸包，那么显然凹进去的点不能是凸包的点 对于每个凸包内的点作极角排序，那么凹进去的两条边必定是相邻两个点与旋转点的连线 剩余的部分还必须要满足凸包的要求 下面通过一个例子来看看所求的面积是哪部分(果然还是得画图，光想就想了一天)

在这里插入图片描述 假设我们此时按照FF点旋转，逆时针排序，为(A,G,E,H,I,B,C,D)(A,G,E,H,I,B,C,D)的顺序

然后我们选择(A,G)(A,G)对凹进去，面积为所有带颜色的区域，如下 在这里插入图片描述 继续遍历，选择(G,E)(G,E)对 在这里插入图片描述 继续遍历(E,H)(E,H)对，因为共线所以直接忽略(PS题目保证没有共线，此处为了仅仅举例)

遍历(H,I)(H,I)在这里插入图片描述 遍历(I,B)(I,B)在这里插入图片描述 可以发现，对于一片区域(1,0,0,0,...,0,1)(1,0,0,0,...,0,1)，即左边和右边都是凸包的点，中间部分非凸包的点，这一部分可以一起计算，每个凹包的面积就是左边的凸包面积(绿色)+右边的凸包面积(红色)+(凸包面积-大三角形面积)(蓝色) 使用前缀和可以维护前缀凸包面积和后缀凸包面积，然后计算 复杂度为O(n2)O(n^2)

cpp
#includebitsstdc++.h
#includeextpb_dsassoc_container.hpp
#includeextpb_dstree_policy.hpp
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define F first
#define S second
#define TR treeint,null_type,lessint,rb_tree_tag,tree_order_statistics_node_update
typedef pairint,int PII;
const int N=2e5+10,M=2e5+10;
const int INF=1e18;
 const int mod=998244353;
const int mod=1e9+7;
mt19937_64 rng(chronosteady_clocknow().time_since_epoch().count());

const double eps=1e-12;
struct Point{
    int x,y,id;
    Point(int x=0,int y=0)x(x),y(y){}
    Point operator-(Point p){return Point(x-p.x,y-p.y);}
    Point operator+(Point p){return Point(x+p.x,y+p.y);}
    bool operator(Point p)const{return x==p.xyp.yxp.x;}
    bool operator==(Point p)const{return x==p.x&&y==p.y;}
    bool operator!=(Point p)const{return x!=p.xy!=p.y;}
    friend ostream& operator(ostream &os, const Point &p) {
        os  (  p.x     p.y  );
        return os;
    }
};
int cross(Point a,Point b){
    return a.xb.y-a.yb.x;
}
int dot(Point a,Point b){
    return a.xb.x+a.yb.y;
}
int area(Point a,Point b,Point c){
    return cross(b-a,c-a);
}
int stk[N],top;
bool used[N];
vectorPoint andrew(vectorPoint &q){
	sort(q.begin(),q.end());
	int n=q.size();
    for(int i=0;in;i++)used[i]=false;
    for(int i=0;in;i++){
        while(top=2&&area(q[stk[top-1]],q[stk[top]],q[i])=0){
            if(area(q[stk[top-1]],q[stk[top]],q[i])0)used[stk[top--]]=false;
            else top--;
        }
        stk[++top]=i;
        used[i]=true;
    }
    used[0]=false;
    for(int i=n-1;i=0;i--){
        if(used[i])continue;
        while(top=2&&area(q[stk[top-1]],q[stk[top]],q[i])=0)top--;
        stk[++top]=i;
    }
	vectorPoint hull;
	for(int i=1;itop;i++)hull.push_back(q[stk[i]]);
	return hull;
}
void solve(){
    int n;
    cinn;
    vectorPoint p(n);
    for(int i=0;in;i++){
        cinp[i].xp[i].y;
        p[i].id=i;
    }
    auto hull=andrew(p);
    vectorint in(n+1);
    for(auto &[x,y,id]hull)in[id]=1;
    int Area=0;
    for(int i=0;ihull.size();i++){
        Area+=cross(hull[i]-hull[0],hull[(i+1)%hull.size()]-hull[0]);
    }
    int ans=0;
    for(int t=0;tn;t++){
        if(in[p[t].id])continue;
        vectorPoint tmp;
        for(int i=0;in;i++){
            if(t==i)continue;
            tmp.push_back(p[i]);
        }
        sort(tmp.begin(),tmp.end(),[&](auto x,auto y){
            if(((x-p[t]).x0)!=((y-p[t]).x0))return (x-p[t]).x(y-p[t]).x;
            return cross(x-p[t],y-p[t])0;
        }); 极角排序
        for(int x=0;xtmp.size();x++){
            if(!in[tmp[x].id])continue;
            int y=x;
            vectorPoint all;
            while(1){
                all.push_back(tmp[y]);
                if(y!=x&&in[tmp[y].id])break;
                y=(y+1)%tmp.size();
            }
            int now=Area-abs(area(p[t],tmp[x],tmp[y]));
            int m=all.size();
            vectorint pre(m),suf(m);
            top=0;
            stk[++top]=0;
            for(int i=1;im;i++){
                if(i)pre[i]=pre[i-1];
                while(top=2&&area(all[stk[top-1]],all[stk[top]],all[i])0){
                    pre[i]-=abs(area(p[t],all[stk[top-1]],all[stk[top]]));
                    top--;
                }
                pre[i]+=abs(area(p[t],all[stk[top]],all[i]));
                stk[++top]=i;
            }
            top=0;
            stk[++top]=m-1;
            for(int i=m-2;i=0;i--){
                suf[i]=suf[i+1];
                while(top=2&&area(all[stk[top-1]],all[stk[top]],all[i])0){
                    suf[i]-=abs(area(p[t],all[stk[top-1]],all[stk[top]]));
                    top--;
                }
                suf[i]+=abs(area(p[t],all[stk[top]],all[i]));
                stk[++top]=i;
            }
            int res=0;
            for(int i=1;im;i++){
                ans=(ans+pre[i-1]+suf[i]+now)%mod;
            }
        }
    }
    coutansn;
}  
signed main(){
    cin.tie(0)-sync_with_stdio(0);
    int T=1;
     cinT;
    while(T--)solve();
    return 0;
}

2023ICPC济南M ​

在这里插入图片描述 题意：

假设能包含所有点的多边形顶点数最少为RR,那么计算能包含所有点的多边形，顶点数为RR或R+1R+1

思路：

显然最少顶点数就是凸包 枚举凸包内的点，极角排序，如果相邻两个点均为凸包的点，那么答案+1 复杂度：O(n2)O(n^2)

cpp
#includebitsstdc++.h
#includeextpb_dsassoc_container.hpp
#includeextpb_dstree_policy.hpp
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define F first
#define S second
#define TR treeint,null_type,lessint,rb_tree_tag,tree_order_statistics_node_update
typedef pairint,int PII;
const int N=2e5+10,M=2e5+10;
const int INF=1e18;
 const int mod=998244353;
const int mod=1e9+7;
mt19937_64 rng(chronosteady_clocknow().time_since_epoch().count());

const double eps=1e-12;
struct Point{
    int x,y,id;
    Point(int x=0,int y=0)x(x),y(y){}
    Point operator-(Point p){return Point(x-p.x,y-p.y);}
    Point operator+(Point p){return Point(x+p.x,y+p.y);}
    bool operator(Point p)const{return x==p.xyp.yxp.x;}
    bool operator==(Point p)const{return x==p.x&&y==p.y;}
    bool operator!=(Point p)const{return x!=p.xy!=p.y;}
    friend ostream& operator(ostream &os, const Point &p) {
        os  (  p.x     p.y  );
        return os;
    }
};
int cross(Point a,Point b){
    return a.xb.y-a.yb.x;
}
int dot(Point a,Point b){
    return a.xb.x+a.yb.y;
}
int area(Point a,Point b,Point c){
    return cross(b-a,c-a);
}
int stk[N],top;
bool used[N];
vectorPoint andrew(vectorPoint &q){
	sort(q.begin(),q.end());
	int n=q.size();
    for(int i=0;in;i++)used[i]=false;
    for(int i=0;in;i++){
        while(top=2&&area(q[stk[top-1]],q[stk[top]],q[i])=0){
            if(area(q[stk[top-1]],q[stk[top]],q[i])0)used[stk[top--]]=false;
            else top--;
        }
        stk[++top]=i;
        used[i]=true;
    }
    used[0]=false;
    for(int i=n-1;i=0;i--){
        if(used[i])continue;
        while(top=2&&area(q[stk[top-1]],q[stk[top]],q[i])=0)top--;
        stk[++top]=i;
    }
	vectorPoint hull;
	for(int i=1;itop;i++)hull.push_back(q[stk[i]]);
	return hull;
}
int sign(int x){
    return x0-1x010;
}
void solve(){
    int n;
    cinn;
    vectorPoint p(n);
    for(int i=0;in;i++){
        cinp[i].xp[i].y;
        p[i].id=i;
    }
    auto hull=andrew(p);
    vectorint onhull(n);
    for(int i=0;ihull.size();i++)onhull[hull[i].id]=1;
    int ans=1;
    for(int t=0;tn;t++){
        if(onhull[p[t].id])continue;
        vectorPoint tmp;
        for(int i=0;in;i++){
            if(i==t)continue;
            tmp.push_back(p[i]);
        }
        sort(tmp.begin(),tmp.end(),[&](auto x,auto y){
            int c=cross(x-p[t],y-p[t]);
            if(c==0)return dot(x-p[t],x-p[t])dot(y-p[t],y-p[t]);
            if(((x-p[t]).x0)!=((y-p[t]).x0))return (x-p[t]).x(y-p[t]).x;
            return c0;
        });
        for(int i=0;itmp.size();i++){
            if(onhull[tmp[i].id]&&onhull[tmp[(i+1)%tmp.size()].id]){
                ans++;
            }
        }
    }
    coutansn;
}  
signed main(){
    cin.tie(0)-sync_with_stdio(0);
    int T=1;
     cinT;
    while(T--)solve();
    return 0;
}

2024CCPC哈尔滨B ​

在这里插入图片描述 题意：

求最大面积的凹包

思路：

如果凸包内没有任何点，无解 当前多边形每选择一个凸包内的点，面积必定会减少；因此最多只会选择一个点凹进去 一个显然的结论是，这个点必定是内部点形成的凸包的点 枚举外凸包的每一条边，找到与该边最近的点，减去这个三角形的面积即为凹包的面积 即找到内凸包的一个点 类似旋转卡壳的思想，当前凸包每旋转到下一条边，内凸包离边最近的点也会跟着旋转，因此双指针维护即可 复杂度O(nlogn)O(n log n)，瓶颈为排序

cpp
#includebitsstdc++.h
#includeextpb_dsassoc_container.hpp
#includeextpb_dstree_policy.hpp
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define F first
#define S second
#define TR treeint,null_type,lessint,rb_tree_tag,tree_order_statistics_node_update
typedef pairint,int PII;
const int N=2e5+10,M=2e5+10;
const int INF=1e18;
 const int mod=998244353;
const int mod=1e9+7;
mt19937_64 rng(chronosteady_clocknow().time_since_epoch().count());

const double eps=1e-12;
struct Point{
    int x,y,id;
    Point(int x=0,int y=0)x(x),y(y){}
    Point operator-(Point p){return Point(x-p.x,y-p.y);}
    Point operator+(Point p){return Point(x+p.x,y+p.y);}
    bool operator(Point p)const{return x==p.xyp.yxp.x;}
    bool operator==(Point p)const{return x==p.x&&y==p.y;}
    bool operator!=(Point p)const{return x!=p.xy!=p.y;}
    friend ostream& operator(ostream &os, const Point &p) {
        os  (  p.x     p.y  );
        return os;
    }
};
int cross(Point a,Point b){
    return a.xb.y-a.yb.x;
}
int dot(Point a,Point b){
    return a.xb.x+a.yb.y;
}
int area(Point a,Point b,Point c){
    return cross(b-a,c-a);
}
int sign(double x){符号函数：精度为eps
	if(fabs(x)=eps) return 0;x为0
	if(x0) return -1;x为负数
	return 1;x为正数
}
int dcmp(double x,double y){
    if(fabs(x-y)=eps) return 0;x与y相等
    if(xy) return -1;x小于y
    return 1;x大于y
}
double get_length(Point a){向量模长（线段长度）
	return sqrt(dot(a,a));
}
typedef Point Vector;
double distance_to_line(Point p,Point a,Point b){点p到直线ab的距离
	Vector v1=b-a,v2=p-a;
	return fabs(cross(v1,v2)get_length(v1));
}
int stk[N],top;
bool used[N];
vectorPoint andrew(vectorPoint &q){
	sort(q.begin(),q.end());
	int n=q.size();
    top=0;
    for(int i=0;in;i++)used[i]=false;
    for(int i=0;in;i++){
        while(top=2&&sign(area(q[stk[top-1]],q[stk[top]],q[i]))0){
            if(sign(area(q[stk[top-1]],q[stk[top]],q[i])0))used[stk[top--]]=false;
            else top--;
        }
        stk[++top]=i;
        used[i]=true;
    }
    used[0]=false;
    for(int i=n-1;i=0;i--){
        if(used[i])continue;
        while(top=2&&sign(area(q[stk[top-1]],q[stk[top]],q[i]))0)top--;
        stk[++top]=i;
    }
	vectorPoint hull;
	for(int i=1;itop;i++)hull.push_back(q[stk[i]]);
	return hull;
}
void solve(){
    int n;
    cinn;
    vectorPoint p(n);
    for(int i=0;in;i++){
        cinp[i].xp[i].y;
        p[i].id=i;
    }
    auto hull=andrew(p);
     for(int i=0;ihull.size();i++)couthull[i]n;
    if(hull.size()==n){
        cout-1n;
        return;
    }
    vectorPoint np;
    vectorint onhull(n);
    for(int i=0;ihull.size();i++){
        onhull[hull[i].id]=1;
    }
    for(int i=0;in;i++){
        if(!onhull[p[i].id])np.push_back(p[i]);
    }
    int Area=0;
    for(int i=0;ihull.size();i++)Area+=cross(hull[i]-hull[0],hull[(i+1)%hull.size()]-hull[0]);
    auto nh=andrew(np);
     for(int i=0;inh.size();i++)coutnh[i]n;
     coutArean;
    int pos=0;
    double ans=INF;
    for(int i=0;inh.size();i++){
        double cur=distance_to_line(nh[i],hull[0],hull[1]);
        if(dcmp(cur,ans)0){
            ans=cur;
            pos=i;
        }
    }
     coutnh[pos]n;
    int res=Area-abs(area(nh[pos],hull[0],hull[1]));
    for(int i=1,j=pos;ihull.size();i++){
        while(dcmp(distance_to_line(nh[j],hull[i],hull[(i+1)%hull.size()]),distance_to_line(nh[(j+1)%nh.size()],hull[i],hull[(i+1)%hull.size()]))0){
            j=(j+1)%nh.size();
        }
        res=max(res,Area-abs(area(nh[j],hull[i],hull[(i+1)%hull.size()])));
    }
    coutresn;
}  
signed main(){
    cin.tie(0)-sync_with_stdio(0);
    int T=1;
    cinT;
    while(T--)solve();
    return 0;
}

2020ICPC南京I ​

在这里插入图片描述 想法很简单，但是对于计算几何苦手来说有点难实现 实际上vxv_x的范围影响到的是速度斜率的大小，斜率kk的范围为frac−vyvxleqkleqfracvyvxfrac{-v_y}{v_x} leq k leq frac{v_y}{v_x}，斜率改变即改变点的移动方向 首先观察到nn很小，最多只有2n2n个点，且不会走回头路，因此按yy排序，考虑dp，dpidp_i表示到当前点的最小速率 因为想要过掉一条线段，如果不能直走通过，那么肯定是刚好擦边线段两边的点过最好，因此我们然后枚举更上层的点jj,判断当前两点的线段是否会和所有线段相交(特判在端点相交，此时算两条边不交)，如果没有与任何线段相交，那么可以到达，计算斜率kk,dpj=min(dpj,max(dpi,k))dp_j=min(dp_j,max(dp_i,k)) 然后对于每个点，判断是否可以直线向上通过区域而不与其他线段相交，如果可以，用当前的点的值更新答案，对答案取最小值 唯一的坑点是，如果你想要走的线路和障碍重合，那么这条线路也是合法的 复杂度O(n3)O(n^3) 官方题解是二分vxv_x，然后判断能不能走到终点

cpp
const double eps=1e-12;
int sign(double x){
    if(fabs(x)=eps) return 0;x为0
    if(x0) return -1;x为负数
    return 1;x为正数
}
struct Point{点坐标
    double x,y;
    int id;
    Point(int x=0,int y=0)x(x),y(y){}
    Point operator-(Point p){return Point(x-p.x,y-p.y);}
    Point operator+(Point p){return Point(x+p.x,y+p.y);}
    Point operator(double k){return Point(xk,yk);}
    Point operator(double k){return Point(xk,yk);}
    double dis(){return xx+yy;}
    int dis(int op){return xx+yy;}
    Point norm(){return thislength();}
    Point vector(){return Point(sign(this-x),sign(this-y));}
    double length(){return sqrt(dis());}
    bool operator(Point p)const{return x==p.xyp.yxp.x;}
    bool operator==(Point p)const{return sign(x-p.x)==0&&sign(y-p.y)==0;}
    bool operator!=(Point p)const{return sign(x-p.x)==0&&sign(y-p.y)==0;}
    friend ostream& operator(ostream &os, const Point &p){
        os(p.x p.y);
        return os;
    }
};
double cross(Point a,Point b){向量叉积
    return a.xb.y-b.xa.y;
}
double dot(Point a,Point b){向量点积
    return a.xb.x+a.yb.y;
}
Point segment_intersection(Point a1,Point a2,Point b1,Point b2){ 判断两个线段a1a2与b1b2是否相交
    double c1=cross(a2-a1,b1-a1),c2=cross(a2-a1,b2-a1);
    double c3=cross(b2-b1,a2-b1),c4=cross(b2-b1,a1-b1);
    if(!(sign(c1)sign(c2)=0&&sign(c3)sign(c4)=0))return {INF,INF};
    Point da=a2-a1,db=b2-b1;
    double d=cross(da,db);
    if(fabs(d)=eps)return {INF,INF};
    double t=cross(b1-a1,db)d;
    double u=cross(b1-a1,da)d;
    if(t=-eps&&t=1+eps&&u=-eps&&u=1+eps){
        return a1+dat;
    }
    return {INF,INF};
}
struct Line{
    Point st,ed;
    Line(Point _st=Point(),Point _ed=Point())st(_st),ed(_ed){}
};
int n,m,vy;
mapint,double dp;
vectorLine line;
vectorPoint p;
void solve(){ 
    cinnmvy;
    for(int i=0;in;i++){
        Point st,ed;
        int sx,sy,ex,ey;
        cinsxsyexey;
        st=Point(sx,sy);
        ed=Point(ex,ey);
        st.id=2i+1;
        ed.id=2i+2;
        if(sign(st.y-ed.y)0)swap(st,ed);
        line.emplace_back(st,ed);
        p.push_back(st);
        p.push_back(ed);
    }
    for(int i=0;ip.size();i++)dp[p[i].id]=INF;
    p.emplace_back(0,-INF);
    p.back().id=INF;
    sort(p.begin(),p.end(),[&](auto a,auto b){
        return a.yb.y;
    });
    for(auto up){
        for(auto vp){
            if(sign(v.y-u.y)=0sign(v.x-m)==0sign(v.x+m)==0)continue;
            bool f=false;
            for(auto lline){
                if(l.st==ul.ed==ul.st==vl.ed==v)continue;
                auto o=segment_intersection(l.st,l.ed,u,v);
                if(sign(o.x-INF)==0)continue;
                f=true;
                break;
            }
            if(f)continue;
            double V=vyfabs((v.y-u.y)(v.x-u.x));
            if(sign(V-dp[u.id])0)V=dp[u.id];
            if(sign(V-dp[v.id])0)dp[v.id]=V;
        }
    }
    double ans=INF;
    coutsetprecision(10)fixed;
    for(auto vp){
        bool flag=false;
        auto P=Point(v.x,INF);
        for(auto lline){
            auto o=segment_intersection(v,P,l.st,l.ed);
            if(sign(o.x-INF)==0)continue;
            if(o==v)continue;
            flag=true;
            break;
        }
        if(flag)continue;
        if(sign(ans-dp[v.id])0)ans=dp[v.id];
    }
    if(sign(ans-INF)==0)cout-1n;
    else coutansn;
}

2021ICPC澳门C ​

在这里插入图片描述在这里插入图片描述在这里插入图片描述 题目的意思可以转化为去掉最少的点，使得剩余的点围成的凸包不包含原点 按原点极角排序，发现剩余的点之间的最大度数不会超过pipi，即判断叉积大于等于0，双指针计算即可

cpp
struct Point{
    int x,y;
};
int cross(Point a,Point b){
    return a.xb.y-a.yb.x;
}
void solve(){ 
    int n;
    cinn;
    vectorPoint p(n);
    for(int i=0;in;i++)cinp[i].xp[i].y;
    sort(p.begin(),p.end(),[&](auto a,auto b){
        if((a.x0)!=(b.x0))return a.xb.x;
        return cross(a,b)0;
    });
    int ans=0;
    for(int i=0,j=0;in;i++){
        while((j+1)%n!=i&&cross(p[i],p[(j+1)%n])=0)j=(j+1)%n;
        if(j=i)ans=max(ans,j-i+1);
        else ans=max(ans,n+j-i+1);
    }
    coutn-ans'n';
}

Wenwei Lin · 2022 — 2025