만드는 중입니다

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

케플러

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

요약
원점을 둘러싼 N개의 원이 만드는 교점의 개수를 셉니다. 교점이 2N개를 넘으면 greater를 출력합니다.
난이도

어려움10점 중 8점

유형
기하, 정렬, 이분 탐색
정답자
아직 제출이 없습니다

문제

이 이상한 행성계에서는 NN개의 행성이 별 주위를 원형 궤도를 따라 돈다. 별은 좌표 (0,0)(0, 0)에 있다. 별은 모든 궤도 원의 내부에 엄격하게 포함되어 있다. 다만 궤도의 중심이 반드시 (0,0)(0, 0)에 있는 것은 아니다.

원형 궤도들은 일반 위치에 있다. 두 궤도가 교차하면 서로 다른 두 점에서 교차한다. 또한 세 궤도가 한 점에서 만나는 경우는 없다.

과학자 João Kepler는 새로운 이론을 검증하려고 한다. 이를 위해 그는 궤도들 사이의 교점 개수를 구해 달라고 부탁했다. 교점의 개수가 2N2N 이하이면 그 값을 구한다. 그렇지 않으면 교점 개수가 2N2N보다 크다는 사실만 알면 된다.

입력

첫 줄에 정수 NN(2≤N≤1500002 \le N \le 150000)이 주어진다. 이는 궤도의 개수다. 이어지는 NN개의 줄에는 실수 세 개 XX, YY, RR이 주어진다. 각각 궤도 중심의 좌표와 반지름이다. 각 실수는 소수점 아래 정확히 3자리로 표기된다. −25.0≤X,Y≤25.0-25.0 \le X, Y \le 25.0이고 1.0≤R≤200000.01.0 \le R \le 200000.0이다.

출력

교점의 개수가 2N2N 이하이면 그 개수를 한 줄에 출력한다. 그렇지 않으면 "greater"를 출력한다.

예제2

  1. 예제 1

    입력
    6
    0.000 1.000 4.000
    0.000 0.000 10.500
    4.000 0.000 6.000
    1.000 1.000 1.750
    -1.000 -1.000 8.000
    2.000 -2.000 4.000
    
    예상 출력
    10
    
  2. 예제 2

    입력
    4
    -1.000 -1.000 3.000
    1.000 -1.000 3.001
    -3.004 3.003 5.002
    1.000 1.000 3.005
    
    예상 출력
    greater