c++ - 一个关于 IntersectingConvexHull 的 topcoder 谜题

Question

我四个小时前第一次问这个问题。事实上，我已经为这个问题搜索了 6 个多小时，但仍然无法理解。

这道题是给你x[n]和y[n]给你n分。您应该找到这些点的两个子集，它们的凸包相交。您的回答应该是满足上述规则的案例数。

You are given a finite set S of points in the plane. For each valid i,one of those points has coordinates (x[i], y[i]). The points are alldistinct and no three of them are collinear.

Below, CH(s) denotes the convex hull of the set s: that is, thesmallest of all convex polygons that contain the set s. We say thatthe ordered pair (s1, s2) is interesting if the following conditionsare satisfied:

1.s1 is a subset of S

2.s2 is a subset of S

3.the sets s1 and s2 are disjoint (i.e., they have no elements in common)

4.the intersection of the convex hulls CH(s1) and CH(s2) has a positive area Note that some points from S may remain unused (i.e.,they will be neither in s1, nor in s2). You are given thecoordinates of all points: the s x and y. Please compute and returnthe number of interesting pairs of sets, modulo 10^9 + 7.

Examples

{1,0,-1,-1,0,1} {1,2,1,-1,-2,-1}

Returns: 14

We have 14solutions:

s1 = {0,1,3}, s2 = {2,4,5} s1 = {0,2,3}, s2 = {1,4,5} s1 ={0,1,4}, s2 = {2,3,5} s1 = {0,2,4}, s2 = {1,3,5} s1 = {1,2,4}, s2 ={0,3,5} s1 = {0,3,4}, s2 = {1,2,5} s1 = {1,3,4}, s2 = {0,2,5} s1 ={0,2,5}, s2 = {1,3,4} s1 = {1,2,5}, s2 = {0,3,4} s1 = {0,3,5}, s2 ={1,2,4} s1 = {1,3,5}, s2 = {0,2,4} s1 = {2,3,5}, s2 = {0,1,4} s1 ={1,4,5}, s2 = {0,2,3} s1 = {2,4,5}, s2 = {0,1,3}

有很多我无法理解的解决方案，以下是其中之一。例如，ccw 有什么用？结果由两部分组成，为什么？能否提供一些算法名称，一些关键字也可以，以便我在google上详细搜索？

这是解决这个问题的一个示例代码:

#include <vector>
#include <iostream>

using namespace std;
const long long mod=1000000007ll;
struct IntersectingConvexHull{
    public:
        int count(vector<int> x, vector<int> y){
            int n = x.size();
            long long P2[110];
            P2[0]=1ll;
            for(int i=1;i<=n;i++){
                P2[i]=P2[i-1]*2%mod;
            }
            long long C[110][110];
            for(int i=0;i<=n;i++){
                C[i][0]=C[i][i]=1ll;
                for(int j=1;j<i;j++){
                    C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
                }
            }
            long long X[100],Y[100];
            for(int i=0;i<=n;i++){
                X[i]=x[i];
                Y[i]=y[i];
            }
            long long ans=0;
            for(int i=0;i<n;i++){
                for(int j=0;j<n;j++){
                    if(i==j)continue;
    
                    int c1=0,c2=0;
                    for(int k=0;k<n;k++){
                        if(k==i||k==j){
                            continue;
                        }
                        long long ccw=(X[i]-X[k])*(Y[j]-Y[k])-(Y[i]-Y[k])*(X[j]-X[k]);
                        if(ccw<0){
                            c1++;
                        }
                        else{
                            c2++;
                        }
                    }
                    if(c1>=2&&c2>=2){
                        ans+=((P2[c1]+mod-c1-1)%mod)*((P2[c2]+mod-c2-1)%mod)%mod;
                        ans%=mod;
                    }
                }
            }
            long long A=0ll;
            for(int i=3;i<=n;i++){
                for(int j=3;j<=n-i;j++){
                    A+=C[n][i]*C[n-i][j]%mod;
                    A%=mod;
                }
            }
            return (A+mod-ans)%mod;

        }
};

Answer 1

两个集合都必须至少有三个点，船体的交点才能具有非零面积。该代码计算满足此条件的分区数减去交叉面积为零的分区数。 (P2 是二的幂。C 是二项式系数。)

当且仅当有一条线将两个凸包分开时，两个凸包的交集面积为零 (Hyperplane separation theorem)。我认为我们需要扩展这个结果，实际上，(在正确的假设下)恰好有两条线将船体分开并接触两者。

最后一个循环计算被减数。之前的计算减数是几何考虑因素的来源。代码遍历所有点对，并考虑通过它们的线，通过带符号的面积测试计算每侧的点数。它增加了从每一侧选择两个或更多点的方法的数量，从而确保，如果我们在一个船体中包含对中的第一个点，在另一个船体中包含对中的第二个点，我们得到两个船体由线支撑和分隔。

我不知道这段代码如何处理退化输入(两个重复点，三个共线点)。