One topcoder puzzle about IntersectingConvexHull

Question

I first asked this question four hours ago. In fact, I have been looking for this question for more than 6 hours, but still can not understand.

This question is about giving you n points, giving you x [n] and y [n]. You should find two subsets of these points whose convex hull intersects. Your answer should be the number of cases that satisfy the above rules.

You are given a finite set of S points on the plane. For each real i, one of these points has coordinates (x [i], y [i]). All points and three of them are not collinear.

Below, CH (s) denotes the convex hull of the set s, i.e. smallest of all convex polygons containing the set s. We say that an 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 do not intersect (that is, they do not have common elements)

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 not be in s1 or s2). You are given the coordinates of all points: sx and y. Please calculate and return the 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 14 solutions:

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 - .)

, , ( ). , , , ( ) , .

minuend. , , - , . , , . , , , .

, ( , ).