[백준] 1711 - 직각삼각형

https://www.acmicpc.net/problem/1711

1711번: 직각삼각형

 

이 문제는 N제한이 1500이고, 1500C3 = 약 5억 6천 이므로 어떻게 커팅을 잘하면 시간제한 5초 안에 해결할 수 있다.

하지만 커팅 과정도 번거롭고 커팅 이후에도 통과가 되지 않을 수 있으므로 유의하며, 다른 방법으로 풀어보자.

 

먼저 직각 삼각형의 정의를 살펴보면, 한 각이 직각인 삼각형이다.

세 점을 어떻게 골랐다 쳐도, 직각인지를 판단해야 한다.

이제부터 이 직각의 판단을, 벡터의 내적으로 구해보려고 한다.

어떤 2차원 평면 상에서 2개의 벡터의 내적이 0이 될 때 두 벡터는 직각을 이루고 있다.

다음과 같은 상황을 가정해보자. 직선을 벡터라 가정하고, 좌표 평면 상에는 총점이 6개 존재하며, 맨 아래 점을 기준으로

총 왼쪽 점 2개 * 오른쪽 점 3개 = 6개의 직각 삼각형이 존재한다.

이외에도 다른 두 벡터 상의 점들로 직각 삼각형을 만들 수 있을 것이다.

그렇다면 어짜피 3중 for-loop을 탐색해야 할 것인데, 어떻게 해결할 것인가? 바로 최대 공약수를 이용하는 것이다.

즉, 왼쪽 점 2개를 1개로 압축시키고, 오른쪽 점 3개를 1개로 압축시키는 것이다.

그래서 위와 같은 결과를 도출해낼 것이다.

생각해 보면, 왼쪽 점 2개는 어차피 같은 직선 벡터 상에서 존재하므로 각각의 x, y 좌표를 최대 공약수로 나누었을 때 같은 값을 가지게 된다.

결론적으로 이 과정을 모든 점에 대해 반복하면 된다.

 

#include <iostream>
#include <algorithm>
#include <map>
using namespace std;

long long gcd(long long a, long long b)
{
	if (b == 0)
		return a;
	return gcd(b, a % b);
}

pair<long long, long long> coor[1500];

int main()
{

	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> coor[i].first >> coor[i].second;
	}
	sort(coor, coor + n);
	int ans = 0;
	for (int i = 0; i < n; i++)
	{
		map<pair<long long, long long>, int> m;
		for (int j = 0; j < n; j++)
		{
			if (i == j)
			{
				continue;
			}
			long long x = coor[i].first - coor[j].first;
			long long y = coor[i].second - coor[j].second;
			long long g = gcd(x, y);
			if (g < 0)
				g = -g;
			x /= g, y /= g;
			m[{x, y}]++;
		}
		for (auto &j : m)
		{
			int nowX = j.first.first;
			int nowY = j.first.second;
			if (m.count({-nowY, nowX}))
			{
				ans += j.second * m[{-nowY, nowX}];
			}
		}
	}
	cout << ans;
}