(1708) 볼록 껍질

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

단계별로 풀어보기

51단계(기하 3) 1번째

 

 

 

가장 작은 볼록 다각형을 구하는 컨벡스 헐, 그 중에서도 그레이엄 스캔을 구현한 알고리즘이다.

PS용으로 쓰기 편하도록 좌표를 나타내는 구조체 Point에 x, y좌표 변수 뿐만 아니라 상대 좌표를 나타내는 변수도 추가한 뒤, 비교 연산을 적절히 설정하여 정렬 함수만으로 기저점 찾기와 반시계 정렬을 할 수 있도록 했다. 상대 좌표 덕분에 반시계 정렬도 실수형 함수나 나눗셈의 정확도 문제 없이 수행할 수 있다.

 

 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;

struct Point{
  long x, y;
  long p, q;
  Point(int x1= 0, int y1= 0): x(x1), y(y1), p(1), q(0) {}
  
  void set(const Point &base){
    p= x-base.x;
    q= y-base.y;
  }

  bool operator <(const Point &A) const {
    if(q*A.p!=p*A.q)  return q*A.p<p*A.q;
    if(p*p+q*q!=A.p*A.p+A.q*A.q)  return p*p+q*q<A.p*A.p+A.q*A.q;
    if(y!=A.y)  return y<A.y;
    return x<A.x;
  }
};

inline long ccw(const Point &p1, const Point & p2, const Point & p3){
  return 1L*(p2.x-p1.x)*(p3.y-p1.y)-1L*(p3.x-p1.x)*(p2.y-p1.y);
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  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++)  p[i].set(p[0]);
  sort(p.begin()+1, p.end());

  stack<int> s;
  s.push(0);  s.push(1);
  
  for(int i=2;i<n;i++){
    while(s.size()>=2){
      int second= s.top();
      s.pop();
      int first= s.top();
        
      if(ccw(p[first],p[second],p[i])>0){
        s.push(second);
        
        break;
      }
    }

    s.push(i);
  }

  cout << s.size();

  return 0;
}