3000. 직각삼각형

3000번: 직각 삼각형

---

아주 단순한 $O(N^{2}\log N)$짜리 풀이법을 생각할 수 있다. 빗변을 이루는 두 점을 고르고, 직각삼각형이 되기 위해 필요한 나머지 한 점이 존재하는지 찾으면 된다. 두 점을 고르는 데 $N^{2}$, 나머지 한 점을 찾는 데 $\log N$ 시간이 걸린다.

 

그러나 $N \le 100,000$이므로 이 풀이를 사용하면 시간 초과. 따라서 조금 더 빠른 풀이를 생각해야 한다. 사실 나도 꽤 오래 걸렸다.

 

``빗변이 아닌 두 변이 좌표축에 평행해야 한다``는 조건에서 힌트를 찾을 수 있다. 즉 내가 점 $(x_{0},~y_{0})$를 고르면, 다른 한 점의 $x$좌표는 $x_{0}$, 또다른 한 점의 $y$좌표는 $y_{0}$이어야 한다. $x$좌표가 $i$인 점의 개수를 $xcount[i]$, $y$좌표가 $j$인 점의 개수를 $ycount[j]$라 하면 구하는 정답은 $\sum{(xcount[x]-1) \times (ycount[y]-1)}$이다. $1$을 빼는 이유는 나머지 점을 고를 때 처음 고른 $(x,~y)$를 제외하고 골라야 하기 때문이다.

 

이 방법으로 같은 삼각형을 중복하여 셀 수도 있을까? 예를 들어 다음의 직각삼각형 $PQR$이 두 번 이상 세어질 수 있는가?

이 직각삼각형은 점 $P$를 먼저 고정했을 때에만 선택될 수 있다. $Q$를 먼저 선택했을 경우에는 $R$을 고를 수 없다. $Q$와 $R$의 $x$좌표와 $y$좌표가 모두 다르기 때문이다. 마찬가지로 $R$을 먼저 선택했을 경우에는 $Q$를 고를 수 없다. 따라서 주어진 직각삼각형은 $P$를 먼저 선택했을 때에만 한 번 세어진다.

---

10등짜리 풀이

실1치고는 꽤 어려운 문제였다.