백준 1711 직각삼각형 (C++)

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

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

vector<pair<long long, long long>> arr;

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    cin >> n;


    arr.resize(n);

    for (auto &item: arr) {
        cin >> item.first >> item.second;
    }

    int ans = 0;

    for (int i = 0; i < n - 2; i++) {
        for (int j = i + 1; j < n - 1; j++) {
            for (int k = j + 1; k < n; k++) {

                long long ij = (arr[j].second - arr[i].second)*(arr[j].second - arr[i].second) + (arr[j].first - arr[i].first)*(arr[j].first - arr[i].first);
                long long ik = (arr[k].second - arr[i].second)*(arr[k].second - arr[i].second) + (arr[k].first - arr[i].first)*(arr[k].first - arr[i].first);
                long long jk = (arr[j].second - arr[k].second)*(arr[j].second - arr[k].second) + (arr[j].first - arr[k].first)*(arr[j].first - arr[k].first);

                if (ij >= ik && ij >= jk) {
                    if (ij == ik + jk) {
                        ans++;
                    }
                } else if (ik >= ij && ik >= jk) {
                    if (ik == ij + jk) {
                        ans++;
                    }
                } else if (jk >= ij && jk >= ik) {
                    if (jk == ij + ik) {
                        ans++;
                    }
                }


            }
        }
    }


    cout << ans;

    return 0;
}

1. 문제

n개의 2차원 상의 좌표가 주어질 때, 이 좌표 중 세 점을 뽑아 만든 삼각형 중 직각삼각형의 개수를 출력하라.

2. 풀이

시간제한이 5초나 주어지므로 브루트포스를 사용하여 풀 수 있다.

    for (int i = 0; i < n - 2; i++) {
        for (int j = i + 1; j < n - 1; j++) {
            for (int k = j + 1; k < n; k++) {

                long long ij = (arr[j].second - arr[i].second)*(arr[j].second - arr[i].second) + (arr[j].first - arr[i].first)*(arr[j].first - arr[i].first);
                long long ik = (arr[k].second - arr[i].second)*(arr[k].second - arr[i].second) + (arr[k].first - arr[i].first)*(arr[k].first - arr[i].first);
                long long jk = (arr[j].second - arr[k].second)*(arr[j].second - arr[k].second) + (arr[j].first - arr[k].first)*(arr[j].first - arr[k].first);

                if (ij >= ik && ij >= jk) {
                    if (ij == ik + jk) {
                        ans++;
                    }
                } else if (ik >= ij && ik >= jk) {
                    if (ik == ij + jk) {
                        ans++;
                    }
                } else if (jk >= ij && jk >= ik) {
                    if (jk == ij + ik) {
                        ans++;
                    }
                }


            }
        }
    }

3중 for문을 사용하여 모든 경우를 탐색한다. 세 변의 길이의 제곱을 각각 구한다. pow 함수는 double을 리턴하여 정확도가 떨어지므로 사용하지 않는다. 좌표의 절댓값이 10억 이하이므로 long long 타입으로 저장한다. 그 후 가장 긴 변의 길이를 구하고, 피타고라스의 정리를 적용하여 정리에 맞을 경우 이를 세어준다. 

 모든 직각삼각형을 세고 이를 출력하면 정답을 구할 수 있다.