[ICPC] 백준 9015 - 정사각형

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

아이디어

정사각형은 네 변의 길이가 같고 내각의 크기가 전부 90도이다.

 

각은 크게 신경 쓰지 않고 일단 두 점이 있을 때 정사각형을 하나 결정한다고 생각해보자.

 

그러면 아래와 같은 경우를 생각할 수 있다.

 

 

두 점을 선택했을 때 오른쪽 위에 정사각형을 만족시키는 두 점이 있는가?로 문제를 좁힐 수 있다.

 

그런데 정사각형을 만족시키는 두 점을 어떻게 선택할까? 두 점의 y 거리와 x 거리를 생각하면 알 수 있다.

 

 

 

P2의 좌표에서 P1의 좌표를 뺀 값을 dx, dy라고 했을 때 위 그림처럼 선택한 두 점에서 x에 dy를 빼고 y에 dx를 더한 좌표에 점이 있는지 확인하면 된다. P2에서 P1을 뺀 것이므로 dy는 음수임을 명심하자.

 

이렇게 구한 두 좌표에 점이 있으면 그것은 정사각형이므로 최대 넓이를 찾아 출력하면 된다. 점이 있는지 확인하는 방법에는 각 점을 set에 넣거나 이진 탐색으로 찾는 방법이 있을 수 있다. 제한 시간이 10초이므로 set을 써도 넉넉하게 정답을 받을 수 있다.

 

전체 코드

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
 
#include "bits/stdc++.h"
#include "ext/rope"
 
using namespace std;
using namespace __gnu_cxx;
 
using ll = long long;
using pii = pair<int, int>;
 
template<typename T>
struct point2 {
  T x, y;
  point2() : x(0), y(0) {}
  point2(T _x, T _y) : x(_x), y(_y) {}
 
  bool operator < (const point2<T> &r) const {
    if (typeid(T) == typeid(int)) {
      if (x != r.x) return x < r.x;
      return y < r.y;
    } else {
      if (fabs(x - r.x) >= 1e-9) return x < r.x;
      return y < r.y;
    }
  }
 
  bool operator == (const point2<T> &r) const {
    if (typeid(T) == typeid(int)) {
      return x == r.x and y == r.y;
    } else {
      return (fabs(r.x - x) < 1e-9 and fabs(r.y - y) < 1e-9);
    }
  }
};
 
inline int dist_sq(point2<int> &l, point2<int> &r) {
  return (r.x - l.x) * (r.x - l.x) + (r.y - l.y) * (r.y - l.y);
}
 
int n;
point2<int> ar[3000];
set<point2<int>> st;
 
void solve()
{
  st.clear();
  cin >> n;
  for (int i = 0; i < n; i++)
  {
    cin >> ar[i].x >> ar[i].y;
    st.insert(ar[i]);
  }
  sort(ar, ar + n);
 
  int ans = 0;
 
  for (int i = 0; i < n; i++)
  {
    for (int j = i + 1; j < n; j++)
    {
      int dx = ar[j].x - ar[i].x;
      int dy = ar[j].y - ar[i].y;
      point2<int> tmp = ar[i];
      tmp.x -= dy;
      tmp.y += dx;
      if (!st.count(tmp)) continue;
 
      tmp = ar[j];
      tmp.x -= dy;
      tmp.y += dx;
      if (!st.count(tmp)) continue;
 
      ans = max(ans, dx * dx + dy * dy);
    }
  }
 
  cout << ans << '\n';
}
 
int main()
{
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
#endif
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
 
  int t;
  cin >> t;
  while (t--)
  {
    solve();
  }
}

제출 기록