BOJ 1708: 볼록 껍질 작성일 2020-03-01 https://www.acmicpc.net/problem/1708 3월동안 210문제 풀기 (5/210) Graham Scan 배워보기 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123#include <bits/stdc++.h> using namespace std; const double EPS = 1e-9; struct Vector { double x, y; Vector() { this->x = 0, this->y = 0; } Vector(int x, int y) { this->x = x, this->y = y; } Vector(const Vector& v1) { x = v1.x, y =v1.y; } Vector& operator+=(const Vector &other) { x += other.x; y += other.y; return *this; } Vector& operator-=(const Vector &other) { x -= other.x; y -= other.y; return *this; } Vector& operator*=(const double C) { x *= C; y *= C; return *this; } Vector& operator/=(const double C) { x /= C; y /= C; return *this; } Vector operator+(const Vector &other) const { return Vector(*this) += other; } Vector operator-(const Vector &other) const { return Vector(*this) -= other; } Vector operator*(const double C) const { return Vector(*this) *= C; } Vector operator/(const double C) const { return Vector(*this) /= C; } }; double cross(Vector v1, Vector v2) { return v1.x * v2.y - v1.y * v2.x; } double ccw(Vector va, Vector vb) { double v = cross(va, vb); if(abs(v) < EPS) return 0; if(v > 0) return 1; if(v < 0) return -1; } double ccw(Vector vr, Vector va, Vector vb) { return ccw(va - vr, vb - vr); } typedef array<Vector, 2> Segment; bool segmentInter(Vector v1, Vector v2, Vector v3, Vector v4) { double v1Root = ccw(v1, v2, v3) * ccw(v1, v2, v4); double v3Root = ccw(v3, v4, v1) * ccw(v3, v4, v2); auto project = [](double x1, double x2, double x3, double x4) { if(x1 > x2) swap(x1,x2); if(x3 > x4) swap(x3,x4); return max(x1,x3) <= min(x2, x4); }; if (v1Root == 0 && v3Root == 0) return project(v1.x, v2.x, v3.x, v4.x) && project(v1.y, v2.y, v3.y, v4.y); return v1Root <= 0 && v3Root <= 0; } bool segmentInter(Segment& s1, Segment& s2) { return segmentInter(s1[0], s1[1], s2[0], s2[1]); } void grahamScan(vector<Vector>& arr, vector<int>& hull) { sort(arr.begin(), arr.end(), [](Vector& v1, Vector& v2) { return v1.y < v2.y || (v1.y == v2.y && v1.x < v2.x); }); Vector origin = arr[0]; for(Vector& v : arr) v -= origin; sort(arr.begin()+1, arr.end(), [](Vector& v1, Vector& v2) { if(ccw(v1, v2) > 0) return true; if(ccw(v1, v2) < 0) return false; return v1.y < v2.y || (v1.y == v2.y && v1.x < v2.x); }); int next = 2; hull = {0,1}; while(next < arr.size()) { while(hull.size() >= 2) { int center = hull.back(); hull.pop_back(); int prev = hull.back(); if(ccw(arr[center], arr[next], arr[prev]) > 0) { hull.push_back(center); break; } } hull.push_back(next++); } } int main() { int N, x, y; scanf("%d", &N); vector<Vector> arr; vector<int> hull; arr.resize(N); for (int i = 0; i < N; i++) { scanf("%d %d", &x, &y); arr[i] = Vector(x,y); } grahamScan(arr, hull); printf("%d", hull.size()); }