[백준 9240] 로버트 후드 (C#, C++) - soo:bak

문제 링크

9240번 - 로버트 후드

설명

평면에 최대 100,000개의 점이 주어질 때, 두 점 사이의 가장 큰 거리를 구하는 문제입니다.

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

접근법

가장 먼 두 점은 항상 볼록 껍질 위에 있습니다. 따라서 먼저 볼록 껍질을 구한 뒤, 껍질 위 점들만으로 최대 거리를 찾으면 됩니다.

볼록 껍질을 구하기 위해 점들을 x 좌표 기준으로 정렬합니다. 정렬된 점들을 왼쪽에서 오른쪽으로 순회하면서 아래 껍질을 만들고, 오른쪽에서 왼쪽으로 순회하면서 위 껍질을 만듭니다. 각 껍질을 만들 때, 새 점을 추가하기 전에 꺾이는 방향이 볼록하지 않으면 이전 점을 제거합니다.

이제 껍질 위에서 가장 먼 두 점을 찾습니다. 껍질의 한 변에서 가장 먼 점을 알고 있으면, 다음 변으로 이동할 때 가장 먼 점도 같은 방향으로만 움직입니다. 따라서 껍질을 한 바퀴 도는 동안 가장 먼 점도 한 바퀴만 돌면 됩니다.

각 변마다 해당 변의 시작점과 현재 가장 먼 점 사이의 거리를 계산하여 최댓값을 갱신합니다. 최종적으로 최대 거리를 출력합니다.

---

Code

C#

using System;
using System.Collections.Generic;
using System.Linq;

namespace Solution {
  struct Point {
    public long X, Y;
    public Point(long x, long y) { X = x; Y = y; }
  }

  class Program {
    static long CCW(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> ConvexHull(List<Point> pts) {
      pts.Sort((p1, p2) => {
        var cx = p1.X.CompareTo(p2.X);
        return cx != 0 ? cx : p1.Y.CompareTo(p2.Y);
      });
      pts = pts.Distinct().ToList();
      if (pts.Count <= 1)
        return pts;

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

      var upper = new List<Point>();
      for (var i = pts.Count - 1; i >= 0; i--) {
        var p = pts[i];
        while (upper.Count >= 2 && CCW(upper[upper.Count - 2], upper[upper.Count - 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 double Diameter(List<Point> hull) {
      var h = hull.Count;
      if (h == 1)
        return 0.0;
      if (h == 2)
        return Math.Sqrt(Dist2(hull[0], hull[1]));

      var j = 1;
      var best2 = 0L;
      for (var i = 0; i < h; i++) {
        var ni = (i + 1) % h;
        while (true) {
          var nj = (j + 1) % h;
          var cross = Math.Abs(CCW(hull[i], hull[ni], hull[nj]));
          var crossNext = Math.Abs(CCW(hull[i], hull[ni], hull[j]));
          if (cross > crossNext)
            j = nj;
          else
            break;
        }
        best2 = Math.Max(best2, Dist2(hull[i], hull[j]));
      }
      return Math.Sqrt(best2);
    }

    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(long.Parse(s[0]), long.Parse(s[1])));
      }
      var hull = ConvexHull(pts);
      var ans = Diameter(hull);
      Console.WriteLine(ans.ToString("0.000000"));
    }
  }
}

C++

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

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

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

typedef vector<Point> vp;

ll ccw(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;
  ll dy = a.y - b.y;
  return dx * dx + dy * dy;
}

vp convexHull(vp& p) {
  sort(p.begin(), p.end());
  p.erase(unique(p.begin(), p.end()), p.end());
  if (p.size() <= 1)
    return p;

  vp lower, upper;
  for (auto& pt : p) {
    while (lower.size() >= 2 && ccw(lower[lower.size() - 2], lower[lower.size() - 1], pt) <= 0)
      lower.pop_back();
    lower.push_back(pt);
  }
  for (int i = (int)p.size() - 1; i >= 0; i--) {
    auto pt = p[i];
    while (upper.size() >= 2 && ccw(upper[upper.size() - 2], upper[upper.size() - 1], 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;
}

double diameter(const vp& h) {
  int n = (int)h.size();
  if (n == 1)
    return 0.0;
  if (n == 2)
    return sqrt((double)dist2(h[0], h[1]));

  ll best2 = 0;
  int j = 1;
  for (int i = 0; i < n; i++) {
    int ni = (i + 1) % n;
    while (true) {
      int nj = (j + 1) % n;
      ll crossCur = abs(ccw(h[i], h[ni], h[j]));
      ll crossNext = abs(ccw(h[i], h[ni], h[nj]));
      if (crossNext > crossCur)
        j = nj;
      else
        break;
    }
    best2 = max(best2, dist2(h[i], h[j]));
  }
  return sqrt((double)best2);
}

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

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

  auto hull = convexHull(p);
  double ans = diameter(hull);

  cout << fixed << setprecision(6) << ans << "\n";

  return 0;
}