[백준 1485] 정사각형 (C#, C++) - soo:bak

문제 링크

1485번 - 정사각형

설명

네 점이 주어질 때, 이들로 정사각형을 만들 수 있는지 판정하는 문제입니다.

접근법

먼저, 정사각형의 성질을 이용합니다. 정사각형은 네 변의 길이가 모두 같고, 두 대각선의 길이도 같으며, 대각선이 변보다 깁니다.

다음으로, 네 점의 모든 쌍에 대해 거리 제곱을 구합니다. 총 6개의 거리가 나오며, 이를 정렬하면 앞의 4개는 변, 뒤의 2개는 대각선에 해당합니다.

이후, 정렬된 거리에서 앞 4개가 모두 같고, 뒤 2개가 모두 같으며, 뒤 2개가 앞 4개보다 크면 정사각형입니다. 또한 변의 길이가 0이 아니어야 중복 점이 없음을 보장합니다.

---

Code

C#

using System;
using System.Collections.Generic;

namespace Solution {
  class Program {
    static long Dist2(long x1, long y1, long x2, long y2) {
      var dx = x1 - x2;
      var dy = y1 - y2;
      return dx * dx + dy * dy;
    }

    static void Main(string[] args) {
      var t = int.Parse(Console.ReadLine()!);
      for (var tc = 0; tc < t; tc++) {
        var x = new long[4];
        var y = new long[4];
        for (var i = 0; i < 4; i++) {
          var s = Console.ReadLine()!.Split();
          x[i] = long.Parse(s[0]);
          y[i] = long.Parse(s[1]);
        }

        var d = new List<long>(6);
        for (var i = 0; i < 4; i++) {
          for (var j = i + 1; j < 4; j++)
            d.Add(Dist2(x[i], y[i], x[j], y[j]));
        }
        d.Sort();

        var ok = d[0] > 0 &&
                 d[0] == d[1] && d[1] == d[2] && d[2] == d[3] &&
                 d[4] == d[5] &&
                 d[4] > d[0];
        Console.WriteLine(ok ? 1 : 0);
      }
    }
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<ll> vl;

ll dist2(ll x1, ll y1, ll x2, ll y2) {
  ll dx = x1 - x2;
  ll dy = y1 - y2;
  return dx * dx + dy * dy;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int T; cin >> T;
  while (T--) {
    ll x[4], y[4];
    for (int i = 0; i < 4; i++)
      cin >> x[i] >> y[i];

    vl d;
    d.reserve(6);
    for (int i = 0; i < 4; i++) {
      for (int j = i + 1; j < 4; j++)
        d.push_back(dist2(x[i], y[i], x[j], y[j]));
    }
    sort(d.begin(), d.end());

    bool ok = (d[0] > 0) &&
              (d[0] == d[1] && d[1] == d[2] && d[2] == d[3]) &&
              (d[4] == d[5]) &&
              (d[4] > d[0]);
    cout << (ok ? 1 : 0) << "\n";
  }

  return 0;
}