c – 关于IntersectingConvexHull的一个topcoder难题

这个问题是通过给你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 all
distinct and no three of them are collinear.

Below,CH(s) denotes the convex hull of the set s: that is,the
smallest of all convex polygons that contain the set s. We say that
the ordered pair (s1,s2) is interesting if the following conditions
are 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 the
coordinates of all points: the s x and y. Please compute and return
the number of interesting pairs of sets,modulo 10^9 + 7.

Examples

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

Returns: 14

We have 14
solutions:

s1 = {0,3},s2 = {2,4,5} s1 = {0,s2 = {1,5} s1 =
{0,4},3,5} s1 = {1,s2 =
{0,s2 = {0,5},4} s1 = {1,4} s1 = {0,s2 =
{1,4} s1 = {2,4} s1 =
{1,3} s1 = {2,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;

        }
};