TBGAME - Two Ball Game

no tags 

Lizarb's national soccer team undoubtedly belongs to the group of favourites to win the World Cup at the upcoming championship. Their greatest advantages are their excellent dribbling skills and the ball passing precision. Particularly, each player can pass the ball to every other player on the playing field at any distance. The team's captain, Oicul, claims that an exercise which certainly has a substantial effect on the team's soccer skills is the so-called "Two-ball Game".

In the two-ball game, n > 4 kickers are positioned on the playing field and do not move (i.e.\ change their locations) during the game. Four of the players are distinguished: two of them, denoted as s1 and s2, are called starting players, and two others, denoted as t1 and t2, are called terminal players. At the beginning, player s1 has got a white ball and s2 possesses a black ball. Then each starting player can kick the ball directly to the corresponding terminal player but he can also kick the ball to any other player on the field and this player can pass the ball to the next one, and so on. The aim is that at the end the white ball is in possession of t1 and the black ball in possession of t2. So, it seems the game is quite simple. However, to avoid ball collisions, the constraint of the game is that no ball trajectories cross each other and that no player (including starting and terminal ones) has more than one ball contact. For simplicity, we assume the trajectory of a ball moving from one player to the next one is a line segment.

Lizarb's national soccer team observed that for some locations of kickers the two-ball game is possible but for some others it is impossible. The figure below shows two example locations: to the left, playing two-ball game is impossible; to the right, playing the game is possible.

example image

Your task is to write a program that checks if for given player locations the two-ball game is possible or not.


Each input starts with a single integer that gives the number of cases that follow. The firsts line of each case contains the number of players n, with 4 ≤ n ≤ 100000 followed by n lines that describe the coordinates of the players. All coordinates are pairwise different and the points determined by the coordinates are not collinear (recall, three or more points are said to be collinear if they lie on a single straight line). The first coordinate describes the location of s1, the second the location of t1, the third coordinate describes the location of s2, and the fourth the location of t2. The remaining coordinates describe positions of other players of the team.


For each case, your algorithm has to output a line containing POSSIBLE if it is possible to play the game and IMPOSSIBLE, otherwise.



2.01 0.02
1.04 3.02
0.01 0.99
4.1  3.2
2.1  2.01
2.01 0.02
1.04 3.02
0.01 0.99
2.1  2.01
4.1  3.2


hide comments
Aditya Kapoor: 2015-08-03 19:21:07

Use scanf instead of cin. Cost me 4 tle. :/

setsquare: 2010-06-30 13:08:44

Thankyou. I was trying some of the different types of algorithms for this problem and the 2nd one actually can't work with collinear points.

Adrian Kuegel: 2010-06-30 10:59:05

You are right, there were two test cases which did not fulfill this constraint, I replaced them.

Last edit: 2010-06-30 12:24:47
setsquare: 2010-06-30 02:09:22

My program is picking up collinear points in the data. It just checks vertical lines (3 points with same x value)

Added by:Adrian Kuegel
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Resource:German Collegiate Programming Contest 2010 (Author: Maciej Liskiewicz)