백준 1708번

오늘 풀어본 문제는 백준의 1708번 문제¹이다. 문제 풀이에 사용한 언어는 C++ 이다.

solved.ac 기준 CLASS

CLASS 6

문제 정보

이 문제의 내용과 조건은 다음과 같다.

문제

다각형의 임의의 두 꼭짓점을 연결하는 선분이 항상 다각형 내부에 존재하는 다각형을 볼록 다각형이라고 한다. 아래 그림에서 (a)는 볼록 다각형이며, (b)는 볼록 다각형이 아니다.

조금만 생각해 보면 다각형의 모든 내각이 $180$ 도 이하일 때 볼록 다각형이 된다는 것을 알 수 있다. 편의상 이 문제에서는 $180$ 도 미만인 경우만을 볼록 다각형으로 한정하도록 한다.

$2$ 차원 평면에 $N$ 개의 점이 주어졌을 때, 이들 중 몇 개의 점을 골라 볼록 다각형을 만드는데, 나머지 모든 점을 내부에 포함하도록 할 수 있다. 이를 볼록 껍질 (CONVEX HULL) 이라 한다. 아래 그림은 $N=10$ 인 경우의 한 예이다.

점의 집합이 주어졌을 때, 볼록 껍질을 이루는 점의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 점의 개수 $N$ $(3 \le N \le 100,000)$ 이 주어진다. 둘째 줄부터 $N$ 개의 줄에 걸쳐 각 점의 $x$ 좌표와 $y$ 좌표가 빈 칸을 사이에 두고 주어진다. 주어지는 모든 점의 좌표는 다르다. $x$ 좌표와 $y$ 좌표의 범위는 절댓값 $40,000$ 을 넘지 않는다. 입력으로 주어지는 다각형의 모든 점이 일직선을 이루는 경우는 없다.

출력

첫째 줄에 볼록 껍질을 이루는 점의 개수를 출력한다.

볼록 껍질의 변에 점이 여러 개 있는 경우에는 가장 양 끝 점만 개수에 포함한다.

풀이과정

1번째 시도

이름에서부터 이 문제가 Convex Hull 알고리즘을 사용하는 문제라는 것을 알 수 있었다.

정확한 알고리즘의 동작 원리와 구현법에 대한 설명은 생략하고, 문제를 해결하기 위해 사용한 방식은 다음과 같다.

입력 받은 점들을 $x$ 좌표의 값이 가장 작은 점을 기준으로 CCW 알고리즘을 이용하여 반시계 방향으로 정렬한다.
std::stack 을 활용하여 Convex Hull 알고리즘을 구현하고, 최종적으로 해당 스택에 Convex Hull 을 구성하는 점들을 저장하게 한다.
스택의 크기를 출력한다.

코드는 다음과 같이 작성하였다. 제출할 때는 헤더파일의 코드를 붙여넣어 제출하였다.

geometric_line.hpp

#ifndef __GEOMETRIC_LINE_HPP__
#define __GEOMETRIC_LINE_HPP__

#include <utility>

template <typename T>
class GeometricLine {
private:
	std::pair<T, T> start;
	std::pair<T, T> end;
public:
	GeometricLine() : start(std::make_pair(0, 0)), end(std::make_pair(0, 0)) {}

	GeometricLine(const std::pair<T, T>& start, const std::pair<T, T>& end) : start(start), end(end) {}

	GeometricLine& operator=(const GeometricLine& other) {
		this->start.first = other.start.first;
		this->start.second = other.start.second;
		this->end.first = other.end.first;
		this->end.second = other.end.second;

		return *this;
	}

	GeometricLine& update(const std::pair<T, T>& newStart, const std::pair<T, T>& newEnd) {
		this->start = newStart;
		this->end = newEnd;
		
		return *this;
	}

	T getCCW(const std::pair<T, T>& target) const {
		return (end.first - start.first) * (target.second - start.second) - (end.second - start.second) * (target.first - start.first);
	}

	bool cross(const GeometricLine& target) {
		const T ourCCW = this->getCCW(target.start) * this->getCCW(target.end);
		const T theirCCW = target.getCCW(this->start) * target.getCCW(this->end);

		if (ourCCW == 0 && theirCCW == 0) {
			if (this->start > target.end || target.start > this->end) {
				return false;
			}
			else {
				return true;
			}
		}
		else {
			return (ourCCW <= 0 && theirCCW <= 0);
		}
	}

	const std::pair<T, T>& getStart(void) const {
		return start;
	}

	const std::pair<T, T>& getEnd(void) const {
		return end;
	}
	
	T lengthSquare(void) const {
	    T dx = end.first - start.first;
	    T dy = end.second - start.second;
	        
	    return dx * dx + dy * dy;
	}
};

#endif // !__GEOMETRIC_LINE_HPP__

main.cpp

#include <bits/stdc++.h>
#include "geometric_line.hpp"

using namespace std;

using ll = long long int;
using ull = unsigned long long int;

using pll = pair<ll, ll>;

class CCW_cmp {
private:
    pll origin;
   
public:
    CCW_cmp(const pll& origin) : origin(origin) {};
    bool operator()(const pll& A, const pll& B) {
        GeometricLine<ll> originToA(origin, A);
        ll ccw = originToA.getCCW(B);
       
        if (ccw < 0) {
            return false;
        }
        else if (ccw > 0) {
            return true;
        }
        else {
            GeometricLine<ll> originToB(origin, B);
            return originToA.lengthSquare() < originToB.lengthSquare();
        }
    }
};

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
   
    int N;
    cin >> N;
   
    vector<pll> points(N);
   
    for (int i=0; i<N; i++) {
        cin >> points[i].first >> points[i].second;
    }
   
    sort(points.begin(), points.end());
   
    CCW_cmp cmp(points[0]);
    sort(points.begin() + 1, points.end(), cmp);
   
    GeometricLine<ll> currentLine(points[0], points[1]);
    stack<pll> convexHull;
   
    convexHull.push(points[0]);
    convexHull.push(points[1]);
   
    for (int i=2; i<N; i++) {
        while (convexHull.size() >= 2) {
            ll ccw = currentLine.getCCW(points[i]);
           
            if (ccw > 0) {
                break;
            }
            else {
                convexHull.pop();
                if (convexHull.size() == 1) {
                    break;
                }
            }
           
            pll B = convexHull.top();
            convexHull.pop();
            pll A = convexHull.top();
            convexHull.push(B);
           
            currentLine = GeometricLine<ll>(A, B);
        }
       
        currentLine = GeometricLine<ll>(convexHull.top(), points[i]);
        convexHull.push(points[i]);
    }
    
    cout << convexHull.size();
   
    return 0;
}

그러자 모든 테스트 케이스를 통과하고 ‘맞았습니다’가 나오는 것을 확인할 수 있었다.

마무리

이 문제는 내가 군입대를 하고 나서 처음으로 푸는 CLASS 6 문제이다. 연등 시간 자체는 짧지만 알차게 활용하여 알고리즘을 공부할 수 있었던 좋은 문제였던 것 같다.

내가 만든 GeometricLine 자료구조는 내 레포지토리²에서 확인할 수 있다. 필요한 사람은 참고하길 바란다.

오늘의 PS는 여기까지!

1: https://www.acmicpc.net/problem/1708
2: https://github.com/ChoiCube84/baekjoon-solutions/blob/main/C%2B%2B/custom_data_structures/geometric_line.hpp

← Previous Post Next Post →