All Tracks Math Problem

Triangle Game
Tag(s):

Easy-Medium, Game Theory, Geometry, approved

Problem
Editorial
Analytics

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.

Constraints

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$$

SAMPLE INPUT
1
7
0 0
3 3
6 6
4 2
6 0
3 1
5 3
SAMPLE OUTPUT
7
Explanation

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$$.

picture!

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++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Scala 2.11.8, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

December Clash '16

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications