LineSegments
TCO10 Round 4 · 2010-04-11 · by keshav_57
TCO10 Round 4 · 2010-04-11 · by keshav_57 · Geometry
Problem Statement
Problem Statement
The prince has just been introduced to geometry in school. The king wants to check his son's progress by giving him the following geometry problem:
You are given the coordinates of N points on the 2-dimensional plane. No two points are coincident and no three are collinear. Find the number of pairs of intersecting line segments whose endpoints are among the given points. The line segments within each pair must not share any common endpoints.
For example, if the given points are {(1, 4), (2, 1), (0, 0), (1, 3) and (2, 4)}, then there are three valid pairs of intersecting line segments as shown in the pictures below.
The king wants you to write a program to solve the above problem so that the answer given by the prince can be checked. The rth point is (xr, yr). The x-coordinates of the points can be generated by using the following recursive definition:
You are given the coordinates of N points on the 2-dimensional plane. No two points are coincident and no three are collinear. Find the number of pairs of intersecting line segments whose endpoints are among the given points. The line segments within each pair must not share any common endpoints.
For example, if the given points are {(1, 4), (2, 1), (0, 0), (1, 3) and (2, 4)}, then there are three valid pairs of intersecting line segments as shown in the pictures below.
The king wants you to write a program to solve the above problem so that the answer given by the prince can be checked. The rth point is (xr, yr). The x-coordinates of the points can be generated by using the following recursive definition:
x1 = xFirst, and
xi = (xi-1*xProd + xAdd) mod xMod, for 2 ≤ i ≤ N
(Note that (xi-1*xProd + xAdd) may overflow 32-bit integers)
The values of yr are defined similarly using yFirst, yAdd, yProd and yMod.Constraints
- N will be between 2 and 1200, inclusive.
- xMod and yMod will be between 1 and 1000000, inclusive.
- xFirst, xAdd and xProd will be between 0 and (xMod-1), inclusive.
- yFirst, yAdd and yProd will be between 0 and (yMod-1), inclusive.
- The values of the arguments will be such that among the N generated points (using the above definition), no two points will be coincident and no three will be collinear.
Examples
0)
6 101080 5500 396324 412247 58495 46559 1680 81684 Returns: 10
1)
5 88874 396279 597237 880235 258031 214893 320708 930580 Returns: 3
2)
9 267352 11896 307137 447945 375427 194282 41875 490478 Returns: 80
3)
7 217366 166352 213623 304880 418434 343792 355233 554631 Returns: 25
4)
2 286304 478063 335016 606832 186861 55432 200484 233630 Returns: 0
80)
4 4 3 1 5 1 1 1 3 Returns: 0
The points are (4, 1), (2, 2), (0, 0) and (3, 1). No intersecting line segments.
83)
4 1 2 1 3 1 1 1 2 Returns: 1
The points are (1, 1), (0, 0), (2, 1) and (1, 0). Line segment {(0, 0), (2, 1)} intersects with line segment {(1, 1), (1, 0)}.
84)
5 1 1 1 3 4 3 2 5 Returns: 3
The example in the problem statement.
90)
6 215657 553897 915611 930784 193666 323425 130393 654599 Returns: 15
Make sure you take care of overflow.
Submissions are judged against all 128 archived test cases, of which 9 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class LineSegments with a public method long long intersections(int N, int xFirst, int xAdd, int xProd, int xMod, int yFirst, int yAdd, int yProd, int yMod) · 128 test cases · 2 s / 256 MB per case