IntersectingConvexHull

SRM 698 (Google) · 2016-08-27 · by cgy4ever

SRM 698 (Google) · 2016-08-27 · by cgy4ever · Geometry

Show categories

Class Name: IntersectingConvexHull

Return Type: int

Method Name: count

Arg Types: (vector<int>, vector<int>)

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.

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.

{-506808, 293802, 524314, -914785, -925973, -861093, -503284, 362928, 881824, 94009, 224837, -421836, -58531, -816289, -205228, -240172, -765972, -385204, -670024, -54291, 334200, 663243, -807349, 32805, 784544, -589344, 646400, -296623, 594397, 991757, 376222, -741538, 904093, -112474, 688393, -267688, -445736, -579969, 989074, 248882, -527743, -429681, -925597, 374210, 197796, -886137, -84431, -87115, -59476, 567363}
{527445, -94457, 534870, 240902, -554238, -858570, 806138, -115352, 607810, 845289, -380664, 975187, 435547, -964261, -186940, -780251, 77354, -18941, -533999, -186134, -843135, 730199, 950351, -466482, -132644, -293253, 29450, -206347, 840762, -22481, 824669, -93083, 133849, -871387, 526288, -617469, -690729, -912302, 925004, 982773, -953942, -247708, -408523, -934629, -487675, 938294, -507595, 274994, 964832, 992988}
Returns: 892109603

Submissions are judged against all 80 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class IntersectingConvexHull with a public method int count(vector<int> x, vector<int> y) · 80 test cases · 2 s / 256 MB per case