레야몬
[C++] 1708번 볼록 껍질 - 기하학, 볼록 껍질 본문
#include <iostream>
#include <algorithm>
#include <stack>
#define LOOP(i, N) for(int i=1; i<=N; i++)
#define MAX_N 100001
using namespace std;
typedef long long ll;
struct VEC { //vector
int x, y;
int p, q;
VEC(int X=0, int Y=0) : x(X), y(Y), p(0), q(0) {}
};
int N; //점의 개수 N
VEC p[MAX_N];
void input()
{
cin >> N;
LOOP(i, N) {
int x, y;
cin >> x >> y;
p[i] = VEC(x, y);
}
}
bool compare(const VEC &a, const VEC &b)
{
if(1LL*a.q*b.p != 1LL*a.p*b.q)
return 1LL*a.q*b.p < 1LL*a.p*b.q;
if(a.y!=b.y) return a.y < b.y;
return a.x < b.x;
}
ll CCW(VEC &a, VEC &b, VEC &c)
{
return 1LL*(a.x*b.y + b.x*c.y + c.x*a.y - a.x*c.y - b.x*a.y - c.x*b.y);
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
input();
sort(p+1, p+N+1, compare); //제일 아래 왼쪽 좌표
LOOP(i, N-1) { //상대 벡터 형성
p[i+1].p = p[i+1].x - p[1].x;
p[i+1].q = p[i+1].y - p[1].y;
}
sort(p+2, p+N+1, compare); //반시계 방향으로 정렬
stack<int> s; s.push(1); s.push(2);
int next = 3;
while(next<=N) {
while(s.size()>=2) {
int a, b;
a = s.top(); s.pop();
b = s.top();
if(CCW(p[a], p[b], p[next]) < 0) { //왼쪽에 있으면 ㄱㅊ
s.push(a);
break;
}
}
s.push(next++);
}
cout << s.size();
return 0;
}
점점... 벡터랑 행렬을 당연하듯이 쓰고 있다. 이게 맞는지는 잘 모르겠는데... 엄.... 그렇다....
볼록 껍질 알고리즘은 처음이라서 다른 사이트를 찾아보면서 공부했다. 참고한 사이트는 아래에 있다.
<Convex Hull Algorithm>
컨벡스 헐 알고리즘(Convex Hull Algorithm)
목차 1. 컨벡스 헐 알고리즘(Convex Hull Algorithm)이란? 2. 컨벡스 헐 알고리즘(Convex Hull Algorithm) 동작 원리 3. 컨벡스 헐 알고리즘(Convex Hull Algorithm) 구현 4. 관련 문제 1. 컨벡스 헐 알고리즘(..
www.crocus.co.kr
<이상한 코드? (풀어야 볼 수 있습니다.)>
https://www.acmicpc.net/source/27512622
로그인
www.acmicpc.net
여기 보면 convex hull algorithm이랑 조금 다른 알고리즘을 사용하는 것 같은 코드가 있는데 12ms가 더 빨리 나왔다. 또 다른 알고리즘인 듯 한데 나중에 공부해봐야겠다.
아 그래프에 그려보면서 문제를 풀면 편하다.
https://www.desmos.com/calculator?lang=ko
Desmos | 그래핑 계산기
www.desmos.com
※현재 고등학교 등교중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다
'알고리즘 > 백준' 카테고리의 다른 글
[C++] 2042번 구간 합 구하기 - 자료 구조, 세그먼트 트리 (0) | 2022.10.04 |
---|---|
[C++] 1786번 찾기 - 문자열, KMP (0) | 2022.10.04 |
[C++] 1533번 길의 개수 - 수학, 분할 정복 (0) | 2022.10.03 |
[C++] 1019번 책 페이지 - 수학 (0) | 2022.10.03 |
[C++] 17387번 선분 교차 2 - 기하학, 많은 조건 분기, 선분 교차 판정 (0) | 2022.10.01 |