[Algorithm] BAEKJOON 1485번: 정사각형 (C++)

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

 

 

 

 

문제

네 점이 주어졌을 때, 네 점을 이용해 정사각형을 만들 수 있는지 없는지를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 네 줄로 이루어져 있으며, 점의 좌표가 한 줄에 하나씩 주어진다. 점의 좌표는 -100,000보다 크거나 같고, 100,000보다 작거나 같은 정수이다. 같은 점이 두 번 이상 주어지지 않는다.

 

출력

각 테스트 케이스마다 입력으로 주어진 네 점을 이용해서 정사각형을 만들 수 있으면 1을, 없으면 0을 출력한다.

 

 

 

 

 

풀이

네 점이 정사각형을 형성하기 위해서는 모든 변의 길이가 같아야 하고, 대각선의 길이가 같아야 한다는 점을 이용하여 해결하였다.

 

 

C++ 소스 코드

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

// 두 점 사이의 거리 제곱을 계산하는 함수
int distSq(pair<int, int> p1, pair<int, int> p2) {
    return (p1.first - p2.first) * (p1.first - p2.first) +
           (p1.second - p2.second) * (p1.second - p2.second);
}

// 네 점이 정사각형을 이루는지 확인하는 함수
bool isSquare(pair<int, int> p1, pair<int, int> p2, pair<int, int> p3, pair<int, int> p4) {
    vector<int> dists;
    dists.push_back(distSq(p1, p2));
    dists.push_back(distSq(p1, p3));
    dists.push_back(distSq(p1, p4));
    dists.push_back(distSq(p2, p3));
    dists.push_back(distSq(p2, p4));
    dists.push_back(distSq(p3, p4));

    // 거리를 정렬한 후
    sort(dists.begin(), dists.end());

    // 가장 작은 4개의 거리(변의 길이)가 같고, 마지막 두 개의 거리(대각선의 길이)가 같다면 정사각형
    return (dists[0] > 0 && dists[0] == dists[1] && dists[1] == dists[2] && dists[2] == dists[3]
            && dists[4] == dists[5]);
}

int main() {
    int T;
    cin >> T; // 테스트 케이스 수 입력
    while (T--) {
        pair<int, int> p1, p2, p3, p4;
        cin >> p1.first >> p1.second;
        cin >> p2.first >> p2.second;
        cin >> p3.first >> p3.second;
        cin >> p4.first >> p4.second;

        // 네 점이 정사각형을 이루는지 확인
        if (isSquare(p1, p2, p3, p4)) {
            cout << 1 << endl;
        } else {
            cout << 0 << endl;
        }
    }
    return 0;
}