IntersectingConvexHull | Topcoder Archive

Problem Statement

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:

s1 is a subset of S
s2 is a subset of S
the sets s1 and s2 are disjoint (i.e., they have no elements in common)
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 int[]s x and y. Please compute and return the number of interesting pairs of sets, modulo 10^9 + 7.

Definition

Class:: IntersectingConvexHull
Method:: count
Parameters:: int[], int[]
Returns:: int
Method signature:: int count(int[] x, int[] y)
(be sure your method is public)

Constraints

x will contain between 6 and 100 elements, inclusive.
x and y will contain the same number of elements.
Each element in x will be between -1,000,000 and 1,000,000, inclusive.
Each element in y will be between -1,000,000 and 1,000,000, inclusive.
All points will be distinct.
No three points will lie on the same line.

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}
```
{444, -646, 367, 302, -506, 810}
```
```
{-530, 660, 872, -78, -621, 77}
```
```
Returns: 10
```
This time we have 10: s1 = {0,1,2}, s2 = {3,4,5} s1 = {0,1,3}, s2 = {2,4,5} s1 = {0,2,3}, s2 = {1,4,5} s1 = {0,2,4}, s2 = {1,3,5} s1 = {2,3,4}, s2 = {0,1,5} s1 = {0,1,5}, s2 = {2,3,4} s1 = {1,3,5}, s2 = {0,2,4} s1 = {1,4,5}, s2 = {0,2,3} s1 = {2,4,5}, s2 = {0,1,3} s1 = {3,4,5}, s2 = {0,1,2}

{-737, -245, -51, 943, -7, 1000, -976, -723}

{-355, 898, -372, -585, -98, -53, 490, -954}

Returns: 900

{-928, 852, 840, 813, -564, -594, -667, 838, -74, -675, -530, -476, -154, 702, 817, 969, 845, 592, 867, -330}

{-898, 682, 604, 22, -452, 901, 464, -624, -272, -792, -906, 36, 249, -287, 871, 877, 446, 910, 943, 427}

Returns: 296398747

Don't forget to mod 10^9+7.

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.