[백준 1708] 볼록 껍질 (C#, C++) - soo:bak

문제 링크

1708번 - 볼록 껍질

설명

N개의 서로 다른 점이 주어집니다. 볼록 껍질을 이룰 때 모서리 위의 중간 점들은 개수에 포함하지 않고, 양 끝점만 포함합니다.

볼록 껍질에 포함되는 점의 개수를 출력하는 문제입니다.

접근법

먼저, 볼록 껍질이란 주어진 모든 점을 포함하는 가장 작은 볼록 다각형입니다. 이를 구하기 위해 점들을 정렬한 뒤 아래 껍질과 위 껍질을 따로 구성하는 방법을 사용합니다.

다음으로, 점들을 x 좌표 기준으로 정렬하고, x가 같으면 y 좌표 기준으로 정렬합니다. 이렇게 정렬하면 가장 왼쪽 점과 가장 오른쪽 점이 양 끝에 위치하게 됩니다.

이후, 아래 껍질을 구성합니다. 정렬된 점들을 왼쪽에서 오른쪽으로 순회하면서 스택에 점을 추가합니다. 이때 새로운 점을 추가하기 전에, 스택의 마지막 두 점과 새 점이 반시계 방향이 아니면 마지막 점을 제거합니다. 반시계 방향 여부는 외적의 부호로 판단하며, 외적이 0 이하이면 시계 방향이거나 일직선이므로 제거합니다.

그 다음, 위 껍질도 같은 방식으로 구성합니다. 이번에는 점들을 오른쪽에서 왼쪽으로 순회하면서 동일한 과정을 반복합니다.

마지막으로, 아래 껍질과 위 껍질을 합칩니다. 이때 양쪽 껍질의 끝점이 서로 중복되므로, 각 껍질에서 마지막 점을 제외하고 합쳐야 합니다. 따라서 전체 볼록 껍질의 점 개수는 아래 껍질 크기와 위 껍질 크기의 합에서 2를 뺀 값입니다.

시간 복잡도는 정렬에 O(N log N), 껍질 구성에 O(N)이므로 전체 O(N log N)입니다.

---

Code

C#

using System;
using System.Collections.Generic;

namespace Solution {
  struct Point : IComparable<Point> {
    public long X, Y;
    public int CompareTo(Point other) {
      var cx = X.CompareTo(other.X);
      return cx != 0 ? cx : Y.CompareTo(other.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 void Main(string[] args) {
      var n = int.Parse(Console.ReadLine()!);
      var pts = new List<Point>(n);
      for (var i = 0; i < n; i++) {
        var p = Console.ReadLine()!.Split();
        pts.Add(new Point { X = long.Parse(p[0]), Y = long.Parse(p[1]) });
      }
      pts.Sort();

      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);
      }

      var hullSize = lower.Count + upper.Count - 2;
      Console.WriteLine(hullSize);
    }
  }
}

C++

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

typedef long long ll;

struct Point {
  ll x, y;
  bool operator<(const Point& other) const {
    if (x != other.x)
      return x < other.x;
    return 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);
}

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;
  sort(p.begin(), p.end());

  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 = n - 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);
  }

  int hullSize = (int)lower.size() + (int)upper.size() - 2;
  cout << hullSize << "\n";

  return 0;
}