반응형

 

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

 

1708번: 볼록 껍질

첫째 줄에 점의 개수 N(3 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 점의 x좌표와 y좌표가 빈 칸을 사이에 두고 주어진다. 주어지는 모든 점의 좌표는 다르다. x좌표와 y좌표의 범

www.acmicpc.net

 

 

 

[ 문제풀이 ]

 

이 문제를 풀기 전에 다음 글을 읽어보고 오시길 추천드립니다!

 

https://rudalsd.tistory.com/66?category=1064608

 

[ 알고리즘 ] 컨벡스 헐 알고리즘(Convex Hull Algorithm)

1. 컨벡스 헐 알고리즘(Convex Hull Algorithm)이란? 컨벡스 헐 알고리즘은 2차원 평면에 여러 개의 점이 있을 때 그 점들 중 일부를 사용하여 볼록 다각형을 만들고 그 안에 나머지 모든 점을 포함시

rudalsd.tistory.com

 

간단하게 문제 풀이 순서에 대해서 알려드리겠습니다.

 

1. y값이 가장 작은 점을 기준점으로 선택합니다.

 

2. 기준점을 기준으로 반시계 방향으로 점들을 정렬합니다.

 

3. 1번 점과 2번 점보다 다음 점이 반시계 방향에 있다면 stack에 넣고, 그렇지 않다면 2번 점을 빼고 다시 3번의 과정을 반복합니다.

 

[ 소스 코드 ]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include<iostream>
#include<algorithm>
#include<stack>
 
#define ll long long
 
using namespace std;
 
struct pos
{
    ll x;
    ll y;
};
 
pos arr[100001];
 
int N;
 
ll ccw(pos a, pos b, pos c)        //점이 직선의 반시계방향에 있으면 양수, 시계방향에 있으면 음수, 일직선상이면 0 return
{
    return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
}
 
bool cmp(pos left, pos right)    //가장 왼쪽 아래에 있는 점 찾기
{
    if (left.y != right.y) return left.y < right.y;
    return left.x < right.x;
}
 
bool cmp2(pos left, pos right)    //가장 왼쪽 아래에 있는 점 기준 반시계방향으로 정렬
{
    ll p = ccw(arr[0], left, right);
    if (p > 0) {
        return true;
    }
    else if (p < 0) {
        return false;
    }
    else {
        if (left.y != right.y) return left.y < right.y;
        return left.x < right.x;
    }
}
 
int main()
{
    cin >> N;
    stack <int> s;
    s.push(0);
    s.push(1);
 
    for (int i = 0; i < N; i++) {
        scanf("%lld %lld", &arr[i].x, &arr[i].y);
    }
 
    sort(arr, arr + N, cmp);
 
    sort(arr + 1, arr + N, cmp2);
 
    int next = 2;
 
    while (next < N)
    {
        while (s.size() >= 2) {        //stack에 점이 2개 이상 있다면
            int second = s.top();
            s.pop();
            int first = s.top();
 
            if (ccw(arr[first], arr[second], arr[next]) > 0) {    //다음 점이 직선의 반시계 방향에 있다면
                s.push(second);
                break;
            }
        }
 
        s.push(next);
        next++;
    }
 
    printf("%d", s.size());
} 
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 1786번 - 찾기 (C++)  (0) 2022.07.20
[ 백준 ] 1761번 - 정점들의 거리 (C++)  (0) 2022.07.18
[ 백준 ] 1086번 - 박성원 (C++)  (0) 2022.07.15
[ 백준 ] 17371번 - 이사 (C++)  (0) 2022.07.14
[ 백준 ] 14428번 - 수열과 쿼리 16 (C++)  (0) 2022.07.13

+ Recent posts

티스토리툴바