PQHulls | Topcoder Archive

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 &lt; i &lt; N+2,
Y[0] = Y0,
Y[i] = (Y[i-1] * YMul + YAdd) % YMod, 0 &lt; i &lt; 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.

Definition

Class:: PQHulls
Method:: countSubsets
Parameters:: int, int, int, int, int, int, int, int, int
Returns:: int
Method signature:: int countSubsets(int N, int X0, int XMul, int XAdd, int XMod, int Y0, int YMul, int YAdd, int YMod)
(be sure your method is public)

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

```
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.
```
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.
```
5
```
```
4
```
```
1
```
```
1
```
```
8
```
```
5
```
```
4
```
```
4
```
```
6
```
```
Returns: 0
```
There can be no nice subsets.

38301228

33476602

42996440

10502745

35649230

12271470

65500929

Returns: 181248946

10323527

10690663

28749177

29744699

60134478

78767213

Returns: 143010383

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.