Connection Status:
Competition Arena > PQHulls

PQHulls

TCO12 Round 3B · 2012-03-27 · by ivan_metelsky

TCO12 Round 3B · 2012-03-27 · by ivan_metelsky · Geometry, Math, Sorting
Class Name: PQHulls
Return Type: int
Method Name: countSubsets
Arg Types: (int, int, int, int, int, int, int, int, int)
Problem Statement

Problem Statement

You are given ints N, X0, XMul, XAdd, XMod, Y0, YMul, YAdd, YMod. Generate N+2 points (X[0], Y[0]), (X[1], Y[1]), ..., (X[N+1], Y[N+1]) as follows: 
X[0] = X0,
X[i] = (X[i-1] * XMul + XAdd) % XMod, 0 < i < N+2,
Y[0] = Y0,
Y[i] = (Y[i-1] * YMul + YAdd) % YMod, 0 < i < N+2.
You can assume that no two of those N+2 points will coincide and no 3 points will lie on the same straight line.

Let S be the set of points 0-th to (N-1)-th, P be the N-th point and Q be the (N+1)-th point. In other words, S = {(X[0], Y[0]), (X[1], Y[1]), ..., (X[N-1], Y[N-1])}, P = (X[N], Y[N]) and Q = (X[N+1], Y[N+1]). A subset T of points from S is called nice if:
  • It contains at least 3 points.
  • The convex hull of points from T contains both P and Q inside itself. (See notes for the definition of "convex hull".)
Return the number of nice subsets, modulo 1,000,000,007.

Notes

  • A set of points A is called convex if for any two points p1 and p2 from A, all points of the line segment p1-p2 also belong to A.
  • A polygon is called convex if its interior is a convex set.
  • A set S is called minimal with respect to a certain property, if this property is true for S, but false for any proper subset of S.
  • The convex hull of a set of points A is the minimal convex set that contains all points from A. The convex hull can be shown to be a convex polygon with all vertices being points from A.

Constraints

  • N will be between 3 and 2,000, inclusive.
  • XMod and YMod will each be between 1 and 100,000,000, inclusive.
  • X0, XMul and XAdd will each be between 0 and XMod-1, inclusive.
  • Y0, YMul and YAdd will each be between 0 and YMod-1, inclusive.
  • No two of the N+2 points (generated as described in the problem statement) will occupy the exact same place.
  • No three of the N+2 points (generated as described in the problem statement) will lie on the same straight line.
Examples
0)
4
3
3
3
10
0
3
2
7
Returns: 3

S = {(3, 0), (2, 2), (9, 1), (0, 5)}. P = (3, 3). Q = (2, 4). A nice subset needs to contain points 2 and 3 and least one of points 0 and 1.

1)
5
1
5
6
8
5
5
3
9
Returns: 5

S = {(1, 5), (3, 1), (5, 8), (7, 7), (1, 2)}. P = (3, 4). Q = (5, 5). 4 nice subsets can be obtained by taking points 0, 1 and 3, and by optionally adding each of the points 2 and 4 to them. One more nice subset consists of points 1, 2, 3 and 4.

2)
5
4
1
1
8
5
4
4
6
Returns: 0

There can be no nice subsets.

3)
99
9461448
38301228
33476602
42996440
10502745
35649230
12271470
65500929
Returns: 181248946
4)
1000
11771634
21704604
13316454
26118772
53463288
55273813
30780036
63626191
Returns: 997658387

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

Coding Area

Language: C++17 · define a public class PQHulls with a public method int countSubsets(int N, int X0, int XMul, int XAdd, int XMod, int Y0, int YMul, int YAdd, int YMod) · 256 test cases · 2 s / 256 MB per case

Submitting as anonymous