CodeForces 1284E New Year and Castle Construction 题解

· · 题解

观察样例发现，四边形可以不是凸的。

对于非凸四边形 ABCD，不妨 C 是凹进去的点，如果点 P 不在四边形内，但是在三角形 BCD 内，因为任三点不共线，可以通过把四边形变成 BDCA 或 CBDA 把点 P 包含在四边形里。因此，如果 ABCDP 五个点的凸包为三角形，则存在两个合法四元子集。

对于凸四边形 ABCD，如果点 P 不在四边形里，显然没办法调整使得它在四边形里。因此若 ABCDP 五个点的凸包为四边形，则存在一个合法四元子集，否则不存在合法四元子集。

改成统计不合法四元子集个数，这相当于统计选出五个点 ABCDE，产生它们构成的凸包的边数之和个不合法的四元子集。

枚举每条边，它所在的直线将平面分成两半，设两半分别有 c_1, c_2 个点，则包含这条边的凸包有 \binom {c_1} 3 + \binom {c_2} 3 个。

用向量积判断点处于哪一半平面，设枚举直线 AB，对于点 P，若 \overrightarrow{AP} \times \overrightarrow{AB} > 0，则 P 在右半平面，否则在左半平面。

拆向量积：

\begin{align*} \overrightarrow{AP} \times \overrightarrow{AB} &> 0 \\ \overrightarrow{AP}_x \cdot \overrightarrow{AB}_y - \overrightarrow{AP}_y \cdot \overrightarrow{AB}_x &> 0 \\ \overrightarrow{AP}_x \cdot \overrightarrow{AB}_y &> \overrightarrow{AP}_y \cdot \overrightarrow{AB}_x \\ \end{align*}

先偷点懒：因为不存在三点共线，所以把 \overrightarrow{AB}_y = 0 或 \overrightarrow{AP}_y = 0 的向量拿出来暴力处理。

然后分类讨论 \overrightarrow{AB}_y, \overrightarrow{AP}_y 的正负号，二分解不等式。

于是可以求出 c_1, c_2。

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

注意分数比大小时也应判断正负号。

#include<iostream>
#include<algorithm>
#include<vector>

#define int long long

using namespace std;

typedef long double ld;

const int o=1e9;

int n;
struct node{
    int x,y,id;
    friend inline node operator-(const node &x,const node &y){
        return {x.x-y.x,x.y-y.y};
    }
}a[2505];
static inline int cross(const node &A,const node &B){
    return A.x*B.y-A.y*B.x;
}

struct frac{
    int p,q;
    friend inline bool operator<(const frac &x,const frac &y){
        if(x.q*y.q<0)
            return x.p*y.q>y.p*x.q;
        return x.p*y.q<y.p*x.q;
    }
};

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;++i){
        cin>>a[i].x>>a[i].y;
        a[i].id=i;
    }
    int ans=n*(n-1)*(n-2)*(n-3)*(n-4)/24; // n * C(n-1, 4)
    for(int i=1;i<=n;++i){
        vector<frac>v1,v2;
        vector<node>ex;
        for(int j=1;j<=n;++j){
            if(i==j)
                continue;
            node x=a[j]-a[i];
            if(x.y==0)
                ex.push_back(x);
            else if(x.y>0)
                v1.push_back({x.x,x.y});
            else
                v2.push_back({x.x,x.y});
        }
        sort(v1.begin(),v1.end());
        sort(v2.begin(),v2.end());
        for(int j=i+1;j<=n;++j){
            node A=a[j]-a[i];
            int c1=0,c2=0;
            if(A.y==0){
                for(int k=1;k<=n;++k){
                    if(i==k||j==k)
                        continue;
                    if(cross(a[k]-a[i],a[j]-a[i])>0)
                        ++c1;
                    else
                        ++c2;
                }
            }else{
                if(A.y>0){
                    c1+=v1.end()-upper_bound(v1.begin(),v1.end(),frac{A.x,A.y});
                    c1+=lower_bound(v2.begin(),v2.end(),frac{A.x,A.y})-v2.begin();
                }else{
                    c1+=lower_bound(v1.begin(),v1.end(),frac{A.x,A.y})-v1.begin();
                    c1+=v2.end()-upper_bound(v2.begin(),v2.end(),frac{A.x,A.y});
                }
                for(auto p:ex){
                    if(p.id==i||p.id==j)
                        continue;
                    if(cross(p,a[j]-a[i])>0)
                        ++c1;
                }
                c2=n-2-c1;
            }
            // c1=c2=0;
            // for(int k=1;k<=n;++k){
            //     if(i==k||j==k)
            //         continue;
            //     if(cross(a[k]-a[i],a[j]-a[i])>0)
            //         ++c1;
            //     else
            //         ++c2;
            // }
            // C(c1, 3) + C(c2, 3)
            ans-=c1*(c1-1)*(c1-2)/6;
            ans-=c2*(c2-1)*(c2-2)/6;
        }
    }
    cout<<ans<<endl;
    return 0;
}