[백준 알고리즘] 3000번: 직각 삼각형
May 05, 2020
3000번: 직각 삼각형
좌표 평면에 점 N개가 있다. 이때, 빗변을 제외한 나머지 두 변이 좌표축에 평행한 직각삼각형을 이루는 점 3개를 고르는 방법을 수를 구하는 프로그램을 작성하시오. 직각삼각형은 한각이 직각인 삼각형이며, 직각의 대변을 빗변이라고 한다.접근 방법:
- 접근 방법 1: 처음 시도했던 방법은 빗변의 갯수를 구하는 방법이었다. 좌표축과 평행하려면 각 3개의 x, y좌표 중 적어도 각각 두 개의 좌표가 같은 위치에 있어야 한다. 따라서 겹치는 점이 아예 없는 좌표들을 빗변으로 생각하고 만들어진 빗변의 양끝점의 x나 y좌표와 일치하는 점을 찾는 방법을 시도했다. 결과는 시간초과였다.
- 접근 방법 2: 좌표축과 평행한 직각삼각형은 두 x좌표가 같은 위치에 있고 동시에 동시에 두 y좌표가 같은 점에 있는 삼각형이다. 그리고 동시에 두 점이 겹치면 안된다. 그래서 각 좌표를 순회하면서 해당 좌표의 x, y에 대해 동일한 x좌표의 갯수, 동일한 y좌표의 갯수를 구한 뒤 두 값을 곱하면 두 x좌표와 y좌표가 겹치는 세개의 좌표의 경우의 수를 구할 수 있다. 결과는 실패..
- 접근 방법 3: 입력이 최대 100000까지 들어오기 때문에 int 형을 long long int 로 바꾸고, 기준이 되는 좌표의 점까지 고려하면 같은 좌표를 가지는 3개의 점까지 경우의 수에 포함되기 때문에 삼각형이 아닌 직선의 좌표들이 들어가게 된다. 기준점 되는 좌표는 제외하고 갯수를 세었다. 결과는 정답!
통과 코드:
#include <cstdio>
#include <vector>
using namespace std;
typedef long long ll;
int main (){
ll N;
vector<ll> xcnt(100001, 0);
vector<ll> ycnt(100001, 0);
vector<ll> vx;
vector<ll> vy;
scanf("%lld", &N);
for (int i = 0 ; i < N ; i++){
ll x, y;
scanf("%lld %lld", &x, &y);
vx.push_back(x);
vy.push_back(y);
xcnt[x]++; // 각 좌표의 갯수 세기
ycnt[y]++;
}
ll total = 0;
for (int i = 0 ; i < N ; i++){
ll sum = (xcnt[vx[i]]-1) * (ycnt[vy[i]]-1); // 한 좌표에 대해서 같은 x나 y를 공유하는 다른 좌표들의 갯수 찾기
if (sum < 0) continue;
total += sum;
}
printf("%lld", total);
return 0;
}
