아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

작도왕 키위새

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

요약
평면 위의 점 N개가 주어질 때 모든 점을 지나는 삼각형의 개수를 구하고, 무한히 많으면 -1을, 유일하면 세 변의 기울기를 출력한다.
난이도

보통10점 중 7점

유형
기하, 수학, 정렬, 구현
정답자
아직 제출이 없습니다

문제

작도왕 키위새는 삼각형을 좋아한다. 2차원 평면 위의 점 NN개가 주어질 때, 모든 점을 지나는 유일한 삼각형을 찾아보자.

입력

첫째 줄에 점의 수 NN이 주어진다. (1≤N≤500,0001 \le N \le 500\\,000)

둘째 줄부터 NN개의 줄에 각 점의 x, y좌표를 나타내는 정수 xx와 yy가 주어진다. (−1,000,000≤x,y≤1,000,000-1\\,000\\,000 \le x, y \le 1\\,000\\,000)

모든 점의 좌표는 서로 다르다.

출력

첫째 줄에 모든 점을 지나는 삼각형의 개수를 출력한다. 무한히 많을 경우 개수 대신 -1을 출력한다.

모든 점을 지나는 삼각형이 유일하다면, 둘째 줄부터 넷째 줄까지 삼각형의 각 변의 기울기를 출력한다.

기울기의 절대 / 상대 오차는 10−610^{-6}까지 허용한다. 삼각형이 유일하면서 어느 한 변의 기울기가 양의 무한대나 음의 무한대인 경우는 주어지지 않는다.

예제9

  1. 예제 1

    입력
    9
    -1 0
    2 0
    3 0
    5 0
    -1 1
    0 2
    1 3
    2 3
    4 1
    
    예상 출력
    1
    1
    0
    -1
    
  2. 예제 2

    입력
    10
    -1 0
    2 0
    3 0
    5 0
    -1 1
    0 2
    1 3
    2 3
    4 1
    2 1
    
    예상 출력
    0
    
  3. 예제 3

    입력
    3
    1 2
    1 3
    1 4
    
    예상 출력
    -1
    
  4. 예제 4

    입력
    5
    0 0
    0 9
    0 10
    2 2
    2 3
    
    예상 출력
    -1
    
  5. 예제 5

    입력
    6
    3 3
    5 3
    6 3
    3 4
    5 5
    8 4
    
    예상 출력
    -1
    
  6. 예제 6

    입력
    6
    -1 1
    1 2
    3 3
    -2 2
    0 4
    2 6
    
    예상 출력
    -1
    
  7. 예제 7

    입력
    7
    -2 2
    -1 1
    0 4
    1 2
    2 6
    3 3
    4 6
    
    예상 출력
    -1
    
  8. 예제 8

    입력
    8
    0 0
    2 1
    4 2
    -2 2
    0 4
    2 6
    3 6
    5 3
    
    예상 출력
    1
    1
    0.5
    -1.5
    
  9. 예제 9

    입력
    7
    -3 -3
    -3 -2
    -3 -1
    0 5
    1 6
    1 7
    1 8
    
    예상 출력
    0