시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
6 초 1024 MB 35 15 10 38.462%

문제

밤하늘을 2차원 좌표평면으로 생각했을 때, 별은 좌표평면 상의 점으로 나타낼 수 있으며, 각자 고유한 수치인 아름다움을 가진다.

별자리란 별 3개를 꼭짓점으로 한 삼각형의 변 위 및 내부의 별들을 뜻한다. 별자리의 아름다움은 별자리의 별들의 아름다움의 합으로 정의한다.

$Q_1+Q_2$일간 천체관측을 진행했다. 각 날마다 다음 두가지 사건 중 하나가 일어났다.

  • $(x_i,y_i)$에 아름다움이 $c_i$인 별이 탄생한다. 현재 별의 개수를 $M$이라 했을 때, 새 별은 별 $M+1$로 명명한다. 이 사건은 $Q_1$번 일어난다.
  • 별 $X,Y,Z$를 꼭짓점으로 하는 별자리를 관측한다. 이 사건은 $Q_2$번 일어난다.

별자리를 관측할 때마다 그 별자리의 아름다움을 구하는 프로그램을 작성해야 한다.

입력

첫 줄에 $Q_1$과 $Q_2$가 공백으로 구분되어 주어진다. $(3 \leq Q_1 \leq 2\,000, 1 \leq Q_2 \leq 1\,000\,000)$

이후 $Q_1+Q_2$개의 줄에 걸쳐 사건들이 주어진다. 각 줄의 첫 수로는 사건의 종류 $t$가 주어진다. $t=1$이면 새 별이 탄생했다는 뜻이고, $t=2$이면 별자리를 관측한다는 뜻이다. 그 후 $t=1$이면 $x_i,y_i,c_i$가, $t=2$이면 $X,Y,Z$가 주어진다. $(-10^9 \leq x_i,y_i \leq 10^9, 1 \leq c_i \leq 10^4, 1 \leq X < Y < Z \leq$ 현재 별의 개수$)$

모든 사건이 끝난 후 한 직선 위에 세 별이 위치한 경우가 없는 입력만 주어진다.

출력

별자리를 관측할 때마다 그 별자리의 아름다움을 구해, 공백으로 구분하여 출력한다.

예제 입력 1

5 5
1 0 0 1
1 1 2 2
1 2 0 4
2 1 2 3
1 1 1 8
2 1 2 3
2 1 2 4
1 2 1 16
2 1 2 3
2 1 2 5

예제 출력 1

7 15 11 15 27

예제 입력 2

7 3
1 5 -1 3
1 -10 9 1
1 2 0 2
1 -7 -2 2
1 4 -3 1
2 1 2 4
1 7 4 3
2 4 5 6
1 -4 -7 3
2 2 6 7

예제 출력 2

8 8 9

출처

High School > 경기과학고등학교 > 나는코더다 2020 송년대회 L번