[백준 2261] 가장 가까운 두 점 (C#, C++) - soo:bak

문제 링크

2261번 - 가장 가까운 두 점

설명

2차원 평면에 최대 100,000개의 점이 주어질 때, 두 점 사이 거리의 제곱 값 중 최솟값을 구하는 문제입니다.

좌표는 정수이며 중복 좌표가 있을 수 있습니다.

접근법

모든 점 쌍을 비교하면 O(N²)이므로 시간 초과가 발생합니다. 효율적인 방법이 필요합니다.

먼저, 점들을 x 좌표 기준으로 정렬합니다. 그 다음 왼쪽에서 오른쪽으로 점을 하나씩 처리하면서 현재까지의 최소 거리를 유지합니다. 이 방식을 스윕라인이라고 합니다.

다음으로, 현재 최소 거리 제곱을 ans라 할 때, x 좌표 차이만으로 이미 거리 제곱이 ans를 넘는 점들은 더 가까워질 수 없습니다. 따라서 x 차이가 루트 ans보다 큰 점들은 후보에서 제거합니다. 이렇게 하면 후보 집합의 크기가 작게 유지됩니다.

이후, 후보 집합을 y 좌표 기준으로 정렬된 상태로 유지합니다. 새 점 p를 처리할 때, y 좌표가 p의 y 좌표에서 루트 ans 범위 내에 있는 점들만 확인하면 됩니다. y 차이만으로 이미 거리 제곱이 ans를 넘는 점들도 더 가까워질 수 없기 때문입니다.

그 다음, 범위 내 각 후보와의 거리 제곱을 계산하여 ans를 갱신합니다. 이 범위 조건 덕분에 각 점당 확인해야 하는 후보 수가 상수로 제한되어 전체 시간 복잡도가 O(N log N)이 됩니다.

마지막으로, 중복 점이 있으면 최소 거리가 0이므로 바로 0을 출력하고 종료합니다. 후보 집합은 균형 트리 자료구조를 사용하여 삽입, 삭제, 범위 탐색이 모두 O(log N)에 수행되도록 합니다.

---

Code

C#

using System;
using System.Collections.Generic;

namespace Solution {
  struct Point {
    public int X, Y;
  }

  class PairComparer : IComparer<(int y, int x)> {
    public int Compare((int y, int x) a, (int y, int x) b) {
      var cy = a.y.CompareTo(b.y);
      if (cy != 0)
        return cy;
      return a.x.CompareTo(b.x);
    }
  }

  class Program {
    static int Dist2(Point a, Point b) {
      var dx = a.X - b.X;
      var dy = a.Y - b.Y;
      return dx * dx + dy * dy;
    }

    static void Main(string[] args) {
      var n = int.Parse(Console.ReadLine()!);
      var pts = new List<Point>(n);
      for (var i = 0; i < n; i++) {
        var s = Console.ReadLine()!.Split();
        pts.Add(new Point { X = int.Parse(s[0]), Y = int.Parse(s[1]) });
      }

      pts.Sort((a, b) => {
        var cx = a.X.CompareTo(b.X);
        if (cx != 0)
          return cx;
        return a.Y.CompareTo(b.Y);
      });

      for (var i = 1; i < n; i++) {
        if (pts[i].X == pts[i - 1].X && pts[i].Y == pts[i - 1].Y) {
          Console.WriteLine(0);
          return;
        }
      }

      var set = new SortedSet<(int y, int x)>(new PairComparer());
      set.Add((pts[0].Y, pts[0].X));
      set.Add((pts[1].Y, pts[1].X));
      var ans = Dist2(pts[0], pts[1]);
      var left = 0;

      for (var i = 2; i < n; i++) {
        while (left < i) {
          var dx = pts[i].X - pts[left].X;
          if (dx * dx <= ans)
            break;
          set.Remove((pts[left].Y, pts[left].X));
          left++;
        }

        var limit = Math.Sqrt(ans);
        var yMin = (int)Math.Ceiling(pts[i].Y - limit);
        var yMax = (int)Math.Floor(pts[i].Y + limit);

        var it = set.GetViewBetween((yMin, int.MinValue), (yMax, int.MaxValue));
        foreach (var p in it)
          ans = Math.Min(ans, Dist2(new Point { X = p.x, Y = p.y }, pts[i]));

        set.Add((pts[i].Y, pts[i].X));
      }

      Console.WriteLine(ans);
    }
  }
}

C++

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

typedef pair<int, int> pii;
typedef vector<pii> vp;

struct Point {
  int x, y;
  bool operator<(const Point& other) const {
    if (x != other.x)
      return x < other.x;
    return y < other.y;
  }
};

int dist2(const Point& a, const Point& b) {
  int dx = a.x - b.x;
  int dy = a.y - b.y;
  return dx * dx + dy * dy;
}

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

  int n; cin >> n;
  vector<Point> p(n);
  for (int i = 0; i < n; i++)
    cin >> p[i].x >> p[i].y;

  sort(p.begin(), p.end());

  for (int i = 1; i < n; i++) {
    if (p[i].x == p[i - 1].x && p[i].y == p[i - 1].y) {
      cout << 0 << "\n";
      return 0;
    }
  }

  set<pii> cand;
  cand.insert({p[0].y, p[0].x});
  cand.insert({p[1].y, p[1].x});
  int ans = dist2(p[0], p[1]);
  int left = 0;

  for (int i = 2; i < n; i++) {
    int dLim = (int)ceil(sqrt((double)ans));

    while (left < i) {
      int dx = p[i].x - p[left].x;
      if (dx * dx <= ans)
        break;
      cand.erase({p[left].y, p[left].x});
      left++;
    }

    auto lower = cand.lower_bound({p[i].y - dLim, INT_MIN});
    auto upper = cand.upper_bound({p[i].y + dLim, INT_MAX});

    for (auto it = lower; it != upper; ++it) {
      Point other{it->second, it->first};
      ans = min(ans, dist2(p[i], other));
    }

    cand.insert({p[i].y, p[i].x});
  }

  cout << ans << "\n";

  return 0;
}