[1485번] 정사각형

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 정사각형인지 구분하는 방법

사실 쉬워보이는 문제이기도 한데, 막상 문제를 풀려면 어떻게 풀어야 할 지 감이 잘 오지 않는 문제이기도 하다.

정사각형인지 구분하는 가장 간단한 방법은 다음과 같다.

방법 1.

각 4변의 길이가 모두 같고, 양 점에서 그은 두 대각선의 길이가 같다면 정사각형이다.

방법 2.

네 점으로 만든 벡터 중 가장 길이가 긴 두 벡터를 고르자.

이때 가장 긴 두 벡터의 각각의 중간 좌표가 같고, 두 벡터의 크기가 같다면 정사각형이다.

아무리 봐도 1번으로 구하기가 쉽지, 2번으로 생각하면 산으로 갈 수 있음을 생각하자..

(방법 1과 방법 2에 대한 두 코드를 수록하겠습니다.)

소스 코드 : 

방법 1.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

#include <iostream> #include <cstdio> #include <algorithm>   using namespace std;   long long x[4], y[4], s[6];   int main() {     int i, j, k, tc;       scanf("%d", &tc);     while (tc--)     {         k = 0;         for (i = 0; i < 4; i++)             scanf("%lld %lld", &x[i], &y[i]);           for (i = 0; i < 4; i++)             for (j = i + 1; j < 4; j++)             {                 s[k] = (x[i] - x[j])*(x[i] - x[j]) + (y[i] - y[j])*(y[i] - y[j]);                 k++;             }           sort(s, s + 6);         printf("%d\n", s[0] == s[1] && s[1] == s[2] && s[2] == s[3] && s[4] == s[5]);     } }     //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus

방법 2.

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <memory.h>
 
using namespace std;
 
typedef pair<int, int> pii;
typedef long long ll;
 
pii p[4];
 
int main()
{
    int tc;
    cin >> tc;
    
    while (tc--)
    {
        memset(p, 0, sizeof(p));
 
        for (int i = 0; i < 4; i++)
            scanf("%d %d",&p[i].first, &p[i].second);
 
 
        vector<pair<double, pair<pii, pii> > > get;
        for (int i = 0; i < 4; i++)
        {
            for (int j = 0; j < 4; j++)
            {
                if (i == j)
                    continue;
 
                int x1 = p[i].first;
                int y1 = p[i].second;
                int x2 = p[j].first;
                int y2 = p[j].second;
                double sz = (double)( (((double)x1 - (double)x2) * ((double)x1 - (double)x2)) + (((double)y1 - (double)y2) * ((double)y1 - (double)y2)) );
                get.push_back({ (double)sz, {{x1,y1},{x2,y2}} });
            }
 
        }
        sort(get.begin(), get.end());
 
        int sz = get.size();
        pair<double, pair<pii, pii> > a = get[sz - 1];
        pair<double, pair<pii, pii> > b = get[sz - 2];
 
        bool chk = true;
        if (a.first == b.first)
        {
            int x1 = a.second.first.first;
            int y1 = a.second.first.second;
 
            int x2 = a.second.second.first;
            int y2 = a.second.second.second;
 
            int x11 = b.second.first.first;
            int y11 = b.second.first.second;
 
            int x22 = b.second.second.first;
            int y22 = b.second.second.second;
 
            if ((((double)x1 + (double)x2) / 2 == ((double)x11 + (double)x22) / 2) && (((double)y1 + (double)y2) / 2 == ((double)y11 + (double)y22) / 2))
            {
                int v1 = x2 - x1;
                int v2 = y2 - y1;
 
                int v11 = x22 - x11;
                int v22 = y22 - y11;
                if (v1*v11 + v2*v22 == 0) {}
                else
                    chk = false;
 
            }
            else
                chk = false;
        }
        else
            chk = false;
 
        if (chk)
            cout << "1" << endl;
        else
            cout << "0" << endl;
    }
    return 0;
}
                chk = false;
        }
        else
            chk = false;
 
        if (chk)
            cout << "1" << endl;
        else
            cout << "0" << endl;
    }
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>