TBGAME  Two Ball Game
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 socalled "Twoball Game".
In the twoball 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 s_{1} and s_{2}, are called starting players, and two others, denoted as t_{1} and t_{2}, are called terminal players. At the beginning, player s_{1} has got a white ball and s_{2} 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 t_{1} and the black ball in possession of t_{2}. 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 twoball game is possible but for some others it is impossible. The figure below shows two example locations: to the left, playing twoball game is impossible; to the right, playing the game is possible.
Your task is to write a program that checks if for given player locations the twoball game is possible or not.
Input
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 s_{1}, the second the location of t_{1}, the third coordinate describes the location of s_{2}, and the fourth the location of t_{2}. The remaining coordinates describe positions of other players of the team.
Output
For each case, your algorithm has to output a line containing POSSIBLE if it is possible to play the game and IMPOSSIBLE, otherwise.
Example
Input: 2 5 2.01 0.02 1.04 3.02 0.01 0.99 4.1 3.2 2.1 2.01 5 2.01 0.02 1.04 3.02 0.01 0.99 2.1 2.01 4.1 3.2 Output: IMPOSSIBLE POSSIBLE
hide comments
Aditya Kapoor:
20150803 19:21:07
Use scanf instead of cin. Cost me 4 tle. :/ 

setsquare:
20100630 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:
20100630 10:59:05
You are right, there were two test cases which did not fulfill this constraint, I replaced them. Last edit: 20100630 12:24:47 

setsquare:
20100630 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 
Date:  20100621 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: NODEJS OBJC PERL6 SQLITE VB.NET 
Resource:  German Collegiate Programming Contest 2010 (Author: Maciej Liskiewicz) 