이동식 저장소

3000. 직각삼각형 본문

Problem Solving/BOJ

3000. 직각삼각형

해스끼 2020. 11. 20. 13:37
 

3000번: 직각 삼각형

첫째 줄에 점의 개수 N(3 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 점의 좌표가 X Y 순서대로 주어진다. (1 ≤ X,Y ≤ 100,000) 겹치는 점은 없다.

www.acmicpc.net


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

 

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

 

빗변이 아닌 두 변이 좌표축에 평행해야 한다는 조건에서 힌트를 찾을 수 있다. 즉 내가 점 (x0, y0)(x0, y0)를 고르면, 다른 한 점의 xx좌표는 x0x0, 또다른 한 점의 yy좌표는 y0y0이어야 한다. xx좌표가 ii인 점의 개수를 xcount[i]xcount[i], yy좌표가 jj인 점의 개수를 ycount[j]ycount[j]라 하면 구하는 정답은 (xcount[x]1)×(ycount[y]1)(xcount[x]1)×(ycount[y]1)이다. 11을 빼는 이유는 나머지 점을 고를 때 처음 고른 (x, y)(x, y)를 제외하고 골라야 하기 때문이다.

 

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

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


10등짜리 풀이

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

'Problem Solving > BOJ' 카테고리의 다른 글

1948. 임계경로  (0) 2020.12.14
3020. 개똥벌레  (0) 2020.12.14
2610. 회의준비  (0) 2020.11.13
10253. 헨리  (0) 2020.10.22
1328. 고층 빌딩  (0) 2020.10.16