만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

풍선 다트

시간 제한1초메모리 제한1024 MB

요약
평면 위의 n개 점을 직선 3개로 모두 지날 수 있는지 판별합니다.
난이도

보통10점 중 6점

유형
기하, 완전 탐색, 구현
정답자
아직 제출이 없습니다

문제

ICPC 대회에서 문제를 하나 풀 때마다 색깔 있는 풍선을 하나씩 받는다. 지난 대회에서 꽤 좋은 성적을 거둬서 지금은 풍선 nn개를 갖고 있다. 이 풍선들을 처리하는 가장 자연스러운 방법은 다트로 모두 터뜨리는 것이다. 하지만 다트는 세 개밖에 없다.

풍선은 평면 위의 고정된 위치에 있는 점으로 모델링된다. 다트를 던질 때마다 어디서 어느 방향으로 던질지 고른다. 다트는 직선으로 날아가면서 경로에 있는 풍선을 모두 터뜨린다.

지난 몇 년간 연습을 많이 해서 다트를 원하는 방향으로 정확히 던질 수 있고, 다트는 무한히 멀리 날아간다. 따라서 누군가 풍선을 모두 터뜨릴 수 있다면 그것은 바로 당신이다. 하지만 재미있는 일을 시작하기 전에, 다트 최대 세 개로 풍선을 모두 터뜨릴 수 있는지 먼저 판단해야 한다.

입력

입력은 다음과 같다.

  • 첫 줄에 정수 nn (1≤n≤1041 \leq n \leq 10^4)이 주어진다. 풍선의 개수다.
  • 다음 nn개의 줄에는 각각 정수 두 개 xx, yy (∣x∣,∣y∣≤109|x|, |y| \leq 10^9)가 주어지며, 이는 풍선의 좌표다.

같은 위치에 놓이는 풍선 두 개는 없다.

출력

다트 세 개로 모든 풍선을 터뜨릴 수 있으면 "possible"을, 그렇지 않으면 "impossible"을 출력한다.

예제3

  1. 예제 1

    입력
    6
    0 0
    1 1
    2 4
    3 9
    4 16
    5 25
    
    예상 출력
    possible
    
  2. 예제 2

    입력
    7
    0 0
    1 1
    2 4
    3 9
    4 16
    5 25
    6 36
    
    예상 출력
    impossible
    
  3. 예제 3

    입력
    7
    -1 -1
    0 0
    1 1
    2 4
    3 9
    4 16
    5 25
    
    예상 출력
    possible