[백준 10254] 고속도로 (C#, C++) - soo:bak

문제 링크

10254번 - 고속도로

설명

여러 도시 중에서 유클리드 거리가 가장 먼 두 도시를 찾는 문제입니다.

접근법

가장 먼 두 점은 항상 점들의 볼록껍질 위에 존재합니다. 따라서 먼저 모든 점을 좌표 기준으로 정렬한 뒤 볼록껍질을 구합니다.

볼록껍질을 구한 후에는 회전하는 캘리퍼스 기법을 사용합니다. 볼록껍질의 한 변을 기준으로 가장 먼 점을 찾고, 변을 하나씩 회전시키면서 반대편 점도 함께 이동시킵니다. 볼록껍질의 성질 덕분에 반대편 점은 한 방향으로만 이동하므로, 모든 쌍을 검사하지 않아도 가장 먼 두 점을 효율적으로 찾을 수 있습니다.

거리 비교는 제곱 거리로 해도 대소 관계가 같으므로 제곱근 계산 없이 정수로 처리할 수 있습니다.

---

Code

C#

using System;
using System.Collections.Generic;

class Program {
  struct Point {
    public long X, Y;
    public Point(long x, long y) { X = x; Y = y; }
  }

  static long Cross(Point a, Point b, Point c) {
    return (b.X - a.X) * (c.Y - a.Y) - (b.Y - a.Y) * (c.X - a.X);
  }

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

  static List<Point> Hull(List<Point> pts) {
    pts.Sort((p1, p2) => {
      var cx = p1.X.CompareTo(p2.X);
      return cx != 0 ? cx : p1.Y.CompareTo(p2.Y);
    });
    var n = pts.Count;
    if (n <= 1) return new List<Point>(pts);

    var lower = new List<Point>();
    foreach (var p in pts) {
      while (lower.Count >= 2 && Cross(lower[^2], lower[^1], p) <= 0)
        lower.RemoveAt(lower.Count - 1);
      lower.Add(p);
    }

    var upper = new List<Point>();
    for (var i = n - 1; i >= 0; i--) {
      var p = pts[i];
      while (upper.Count >= 2 && Cross(upper[^2], upper[^1], p) <= 0)
        upper.RemoveAt(upper.Count - 1);
      upper.Add(p);
    }

    lower.RemoveAt(lower.Count - 1);
    upper.RemoveAt(upper.Count - 1);
    lower.AddRange(upper);
    return lower;
  }

  static void Main() {
    var T = int.Parse(Console.ReadLine()!);
    var output = new System.Text.StringBuilder();
    while (T-- > 0) {
      var n = int.Parse(Console.ReadLine()!);
      var pts = new List<Point>(n);
      for (var i = 0; i < n; i++) {
        var parts = Console.ReadLine()!.Split();
        var x = long.Parse(parts[0]);
        var y = long.Parse(parts[1]);
        pts.Add(new Point(x, y));
      }

      var hull = Hull(pts);
      var m = hull.Count;
      var a = hull[0];
      var b = hull[Math.Min(1, m - 1)];
      if (m == 2) {
        output.AppendLine($"{a.X} {a.Y} {b.X} {b.Y}");
        continue;
      }

      var best = 0L;
      var j = 1;
      for (var i = 0; i < m; i++) {
        var ni = (i + 1) % m;
        while (true) {
          var nj = (j + 1) % m;
          var cross = Cross(
            new Point(0, 0),
            new Point(hull[ni].X - hull[i].X, hull[ni].Y - hull[i].Y),
            new Point(hull[nj].X - hull[j].X, hull[nj].Y - hull[j].Y)
          );
          if (cross > 0) j = nj;
          else break;
        }
        var d = Dist2(hull[i], hull[j]);
        if (d > best) { best = d; a = hull[i]; b = hull[j]; }
      }

      output.AppendLine($"{a.X} {a.Y} {b.X} {b.Y}");
    }
    Console.Write(output.ToString());
  }
}

C++

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

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

ll cross(const Point& a, const Point& b, const Point& c) {
  return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

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

vector<Point> convexHull(vector<Point>& p) {
  sort(p.begin(), p.end());
  int n = p.size();
  if (n <= 1) return p;
  vector<Point> lower, upper;
  for (auto& pt : p) {
    while (lower.size() >= 2 && cross(lower[lower.size()-2], lower.back(), pt) <= 0)
      lower.pop_back();
    lower.push_back(pt);
  }
  for (int i = n - 1; i >= 0; --i) {
    auto pt = p[i];
    while (upper.size() >= 2 && cross(upper[upper.size()-2], upper.back(), pt) <= 0)
      upper.pop_back();
    upper.push_back(pt);
  }
  lower.pop_back();
  upper.pop_back();
  lower.insert(lower.end(), upper.begin(), upper.end());
  return lower;
}

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

  int T; cin >> T;
  while (T--) {
    int n; cin >> n;
    vector<Point> pts(n);
    for (auto& pt : pts) cin >> pt.x >> pt.y;

    vector<Point> h = convexHull(pts);
    int m = h.size();
    Point a = h[0], b = h[min(1, m-1)];
    if (m == 2) {
      cout << a.x << " " << a.y << " " << b.x << " " << b.y << "\n";
      continue;
    }

    ll best = 0;
    int j = 1;
    for (int i = 0; i < m; i++) {
      int ni = (i + 1) % m;
      while (true) {
        int nj = (j + 1) % m;
        ll cx = cross({0,0},
                      {h[ni].x - h[i].x, h[ni].y - h[i].y},
                      {h[nj].x - h[j].x, h[nj].y - h[j].y});
        if (cx > 0) j = nj;
        else break;
      }
      ll d = dist2(h[i], h[j]);
      if (d > best) { best = d; a = h[i]; b = h[j]; }
    }

    cout << a.x << " " << a.y << " " << b.x << " " << b.y << "\n";
  }

  return 0;
}