All Tracks Math Problem

Triangle Game

Easy-Medium, Game Theory, Geometry, approved


Alice and Bob are playing a game on a set of points in the 2 dimensional plane.

Initially, there are N points.

In the beginning, 3 points are chosen as starting points to make the initial triangle of the game. These three points must not be collinear, and all points that lie on the boundary of the triangle or outside this triangle are erased.

Alice and Bob then play a game on this initial triangle and remaining points with Alice going first.

On a player's turn, the player first chooses a triangle(say \(\Delta ABC\)) which is still in the game and has at least one point strictly inside.
Then the player chooses any point P strictly inside the \(\Delta ABC\). \(\Delta ABC\) is now removed from the game. The move introduces 3 new smaller triangles \(\Delta ABP\), \(\Delta APC\) and \(\Delta PBC\) into the game. The game continues on the remaining points and triangles.

The loser of the game is the one who is unable to move on their turn.

Given the set of points, compute the number of initial three points such that Alice wins if both players play optimally. Two initial sets of points are different if the unordered sets of the points are different.

Input Format:

The first line will contain the number of test cases T.
Each test case will be formatted as follows.
The first line will contain a single integer N.
The next N lines will describe two integers \(x_i, y_i\) denoting the coordinates of a point in the 2 dimensional plane.

Output Format:

Output T numbers, the number of initial configurations that lead to a win for Alice.


For all subtasks:
\(T ≤ 100\)
\(0 ≤ x_i,y_i ≤ 10^9\)
\(3 ≤ N\)

File 1 (60 pts)
\(N ≤ 7\)

File 2 (40 pts)
\(N ≤ 30\)

0 0
3 3
6 6
4 2
6 0
3 1
5 3

This is a picture of the first sample. The initial triangles that will lead to Alice's win are \(ABE\), \(ACE\), \(ADE\), \(AEG\), \(BCE\), \(CDE\), \(CEF\).


For the game that starts with the triangle \(ACE\), one possible game play looks like this:

The initial triangle is chosen, and invalid points are erased.

enter image description here

Alice chooses point D.

enter image description here

Bob chooses point F.

enter image description here

Alice chooses point G.

enter image description here

At this point, Bob has no available moves, so Bob loses.

Time Limit: 5.0 sec(s) for each input file.
Memory Limit: 512 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic


Initializing Code Editor...
Your Rating:


This Problem was Asked in


Challenge Name

December Clash '16

View All Notifications