역삼각형

당연하지만, 조건을 만족하는 역삼각형의 개수는 $cal(O)(N^3)$개이기 때문에 모든 $a$, $b$, $c$를 순회하며 조건을 만족하는지 검사하는 것은 불가능합니다.

역삼각형을 구성하는 세 점 $a$, $b$, $c$ 중, $b$에 해당하는 점을 고정해 봅시다. $a$, $b$, $c$는 문제 본문에서 제시된 조건을 모두 만족하는 점들입니다.

우선 역삼각형 하나의 넓이를 계산해봅시다. $a$와 $b$의 $x$ 좌표 차를 $p$, $b$와 $c$의 $x$ 좌표 차를 $q$라고 하고, 유사하게 $y$ 좌표의 차도 $r$, $s$로 정의하겠습니다.

$b$를 지나고 $x$축에 평행한 직선과 $a$, $c$를 각각 지나고 $y$축에 평행한 직선을 생각해봅시다. 이 직선들과 $a$, $c$를 잇는 선분은 사다리꼴을 이룹니다.

역삼각형의 넓이는 사다리꼴에서 양쪽의 직각삼각형 넓이를 뺀 것과 같습니다.

계산의 편의상 모든 넓이에 $2$를 곱한 것으로 생각합시다. 사다리꼴의 넓이는 $(p + q)(r + s)$ 이고, 직각삼각형의 넓이는 각각 $p r$, $q s$ 이므로 역삼각형의 넓이는 $p s + q r$ 이 됩니다.

$b$를 고정했으므로 가능한 $a$와 $c$에 해당하는 점을 고르는 것은 독립적입니다. $a$로 가능한 점의 개수를 $L$, $c$로 가능한 점의 개수를 $R$ 이라고 합시다. 만들어질 수 있는 모든 역삼각형의 넓이의 합은 다음과 같습니다.

$sum_(i=1)^(L) sum_(j=1)^(R) (p_i s_j + q_j r_i)$

$eq (sum_(i=1)^(L) p_i)(sum_(j=1)^(R) s_h) + (sum_(j=1)^(R) q_j)(sum_(i=1)^(L) r_i)$

결론적으로, 모든 점에 대해 아래 네 개의 값을 알고 있으면 총 $cal(O)(N)$ 시간에 모든 역삼각형의 넓이 합을 구할 수 있습니다.

1. 현재 점보다 왼쪽 위에 있는 모든 점과 $x$ 좌표 차의 합
2. 현재 점보다 왼쪽 위에 있는 모든 점과 $y$ 좌표 차의 합
3. 현재 점보다 오른쪽 위에 있는 모든 점과 $x$ 좌표 차의 합
4. 현재 점보다 오른쪽 위에 있는 모든 점과 $y$ 좌표 차의 합

네 개의 값 모두 스위핑과 세그먼트 트리를 이용해 전처리할 수 있습니다.

점들을 $y$ 좌표 내림차순으로 정렬한 뒤 계산해주면 됩니다. 이때, 같은 $y$ 좌표를 가지는 점들은 계산 결과에 포함하지 않도록 유의해야 합니다. 총 시간복잡도는 $cal(O)(N log N)$ 입니다.