题解：P16320 [ICPC 2023 Jinan R] 近似凸多边形

· · 题解

Solution

首先有一个近似凸多边形即为点集 S 的凸包，那么显然凸包就是顶点最少的近似凸多边形 R。又因为要求 |Q|\le|R|+1，所以最多再加一个点。

观察样例不难发现满足的近似凸多边形就是将凸包的一条边替换为与凸包内一点组成的三角形，否则其他情况必然会使某个凸包顶点处于当前多边形之外。因此当前的任务就是枚举每一条凸包上的边，统计凸包内有多少个点与之组成的三角形内部没有其他点。

假设当前枚举的凸包上的边为 AB，枚举的凸包内点为 C。若存在某个点 D 在 \triangle ABC 内部，则有 \angle ABD<\angle ABC,\angle BAD<\angle BAC。这就是一个二维偏序，那么我们枚举一条边 AB 时，将所有凸包内点 C 按 \angle ABC 从小到大排序，检查 \angle BAC 是否小于排在 C 所有前面的点 D 的 \min\angle BAD 即可。

时间复杂度 \mathcal O(n^2\log n)。

Code

至于代码实现，可以用向量求角度的 \cos 值。注意最好不要用斜率求 \tan 值来代替，因为会出现斜率不存在的清况。

#include<bits/stdc++.h>
using namespace std;
namespace io{快读}using namespace io;
const int N=2005;
#define db double
const db eps=1e-10;
int n,m;
#define int long long
struct node{
    int x,y;
    node operator-(node u){return {x-u.x,y-u.y};}
    int operator*(node u){return x*u.y-y*u.x;}
    db operator^(node u){
        db L=sqrt(x*x+y*y),Lu=sqrt(u.x*u.x+u.y*u.y);
        return (x*u.x+y*u.y)/(L*Lu);
    }
}a[N],h[N];
int tp,S[N];
bool is[N];
void init(){
    sort(a+1,a+n+1,[](node u,node v){return u.x==v.x?u.y<v.y:u.x<v.x;});
    S[tp=1]=1;
    for(int i=2;i<=n;i++){
        while(tp>1&&(a[S[tp]]-a[S[tp-1]])*(a[i]-a[S[tp]])<=0)is[S[tp--]]=0;
        is[i]=1;S[++tp]=i;
    }int tmp=tp;
    for(int i=n-1;i;i--)if(!is[i]){
        while(tp>tmp&&(a[S[tp]]-a[S[tp-1]])*(a[i]-a[S[tp]])<=0)is[S[tp--]]=0;
        is[i]=1;S[++tp]=i;
    }
    for(int i=1;i<=tp;i++)h[i]=a[S[i]];
    m=tp-1;
}
const db PI=acos(-1);
main(){
    read(n);
    for(int i=1;i<=n;i++)read(a[i].x,a[i].y);
    init();
    int ans=0;
    for(int i=1;i<=m;i++){
        vector<pair<db,db>>V;
        node P2=h[i]-h[i+1],P1=h[i+1]-h[i];
        for(int k=1;k<=n;k++)if(!is[k]){
            db k1=P1^(a[k]-h[i]),k2=P2^(a[k]-h[i+1]);
            V.push_back({k1,k2});
        }
        sort(V.begin(),V.end());
        if(V.empty())continue;
        db mx=-2;
        for(int i=n-m-1;i>=0;i--){
            if(mx<=V[i].second-eps)ans++;
            mx=max(mx,V[i].second);
        }
    }printf("%lld\n",ans+1);
    return 0;
}