[백준/C++/Silver(3)] 1485 - 정사각형

1485번: 정사각형

 

본인이 해당 문제의 출제자가 아니며, 문제 자체에 대한 모든 사항은 위의 링크가 출처임을 명시합니다.

 

정사각형~

 

이번에도 모자란 기하학 계열 문제를 풀어보러 왔다.

 

문제는 이렇다 : 

 단순하게 4개의 2차원 좌표평면의 좌표가 정사각형을 이루는지 알아내면 되는 문제였다. 

 

입력은 이렇다 :

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

 

생각 : 

“정사각형의 정의”는 네 변의 길이가 같고 네 내각의 크기가 같은 사각형 이지만, 좌표점을 주었을때 각도를 알아내기란 여간 성가신 일이 아니다. 그래서 그런 것 말고, 다른 조건을 조합해서 알아내는 것이 좋겠다고 생각했다. 학창시절에 배운 “어떤 사각형이 직사각형이 되는 조건”에는 “한 쌍의 변이 서로 평행하며 대각선의 두 길이가 같을 때”도 있었던 것이 기억이 났다.

 

 그래서 우선 평행한 한 쌍의 변을 찾기로 했는데, 이는 backtracking을 이용하기로 했다. 0~3까지로 이루어진 중복이 없는 순열을 만들어 주는 코드를 짜보았다.

 

코드 1 (backtrack 0~3 중복 X 순열 생성) : 

void backtrack(int curr){
    if(curr > 3) {
        if(dists[made[0]][made[1]] == dists[made[2]][made[3]]){
            a = made[0];
            b = made[1];
            c = made[2];
            d = made[3];
            end_backtrack = true;
        }
        return;
    }
    for(int i = 0; i < 4 && !end_backtrack; i++){
        if(!is_visited[i]){
            is_visited[i] = true;
            made[curr] = i;
            backtrack(curr + 1);
            is_visited[i] = false;
        }
    }
}

다른 여타 백트랙과는 다르게 끝까지 트래킹을 하지는 않는데, 한쌍의 평행한 두 선분만 알면 되고 나머지는 필요 없기 때문이다. 이렇게 해서 코스트를 좀 더 아낄 수 있다.

 

여기서 dist[ i ][ j ]는 입력된 (i 번째 좌표) - (j 번째 좌표)를 해서 나온 값이다. 그럼 같은 기울기를 가진 서로 다른 선분 2개를 알아낼 수 있으며, 그 선분을 기준으로 계산을 시작하기로 했다.

 

a→b, c→d 선분이 평행하므로, a→d 와 b→c 선분의 길이가 같으면 직사각형이라고 할 수 있다. 거기다가 a→b 와 a→c 선분의 길이가 같으면 인접한 두변의 길이 같은 직사각형이므로 정사각형임을 특정할 수 있다!

 

우선 두 점사이의 유클리드 거리를 계산하는 함수를 미리 작성해두었다.

코드 2 (유클리드 거리 구하기) : 

double eu_dist(Cord a, Cord b){
    double euclid_distance = (double)(b.first - a.first) * (b.first - a.first)
        + (b.second - a.second) * (b.second - a.second);
    euclid_distance = sqrt(euclid_distance);
    return euclid_distance;
}

 

그리고 메인 솔루션 함수를 작성했다. 여기서는 dist[ i ][ j ] 를 계산하고 한쌍의 평행한 변을 찾고, 대각선의 길이와 인접한 두변의 길이 같은 지를 한번에 테스트 한다.

코드 3 (메인 솔루션 함수) : 

a = b = c = d = -1;
end_backtrack = false;
backtrack(0);

//cout << a << b << c << d << '\n';

//평행하며, 길이가 같은 한짝의 선분을 찾지 못함
if(a < 0){
    cout << "0\n";
    return;
}
//평행하며, 길이가 같은 한짝의 선분을 찾음
//직사각형 조건 확인 두 대각선 길이 같음 여기서 인접한 두 변의 길이 같음
if(eu_dist(cords[b], cords[c]) == eu_dist(cords[a], cords[d]) &&
    eu_dist(cords[a], cords[b]) == eu_dist(cords[a], cords[c])){
    cout << "1\n";
} else {
    cout << "0\n";
}

그리고 해당 코드를 제출했는데 단번에 맞았습니다!를 볼 수 있었다. 나름 뿌듯했다.

 

FULL 코드 : 

#include <iostream>
#include <cmath>

using namespace std;

#define Cord pair<int, int>

Cord cords[5] = {};
Cord dists[5][5] = {};
bool is_visited[5] = {0};
int made[5] = {0};

int a, b, c, d;
bool end_backtrack = false;

Cord dist(Cord a, Cord b){
    a.first -= b.first;
    a.second -= b.second;
    return a;
}

double eu_dist(Cord a, Cord b){
    double euclid_distance = (double)(b.first - a.first) * (b.first - a.first)
        + (b.second - a.second) * (b.second - a.second);
    euclid_distance = sqrt(euclid_distance);
    return euclid_distance;
}

void backtrack(int curr){
    if(curr > 3) {
        if(dists[made[0]][made[1]] == dists[made[2]][made[3]]){
            a = made[0];
            b = made[1];
            c = made[2];
            d = made[3];
            end_backtrack = true;
        }
        return;
    }
    for(int i = 0; i < 4 && !end_backtrack; i++){
        if(!is_visited[i]){
            is_visited[i] = true;
            made[curr] = i;
            backtrack(curr + 1);
            is_visited[i] = false;
        }
    }
}

void solution(){
    for(int i = 0; i < 4; i++){
        cin >> cords[i].first >> cords[i].second;
    }
    
    for(int i = 0; i < 4; i++){
        for(int j = 0; j < 4; j++){
            if(i != j)
                dists[i][j] = dist(cords[i], cords[j]);
        }
    }
    
    a = b = c = d = -1;
    end_backtrack = false;
    backtrack(0);
    
    //cout << a << b << c << d << '\n';
    
    //평행하며, 길이가 같은 한짝의 선분을 찾지 못함
    if(a < 0){
        cout << "0\n";
        return;
    }
    //평행하며, 길이가 같은 한짝의 선분을 찾음
    //직사각형 조건 확인 두 대각선 길이 같음 여기서 인접한 두 변의 길이 같음
    if(eu_dist(cords[b], cords[c]) == eu_dist(cords[a], cords[d]) &&
        eu_dist(cords[a], cords[b]) == eu_dist(cords[a], cords[c])){
        cout << "1\n";
    } else {
        cout << "0\n";
    }
    
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    
    //backtrack(0);
    while(t--){
        solution();
    }

    return 0;
}