# 기하알고리즘

3개의 포스트
post-thumbnail

백준 2166 다각형의 면적

문제 n개의 점(x, y로 나타냅니다.)으로 이루어진 다각형의 면적을 구하세요 n (1 ≤ n ≤ 1만) 정점의 수 1만 이하 좌표의 크기 10만이하 시간 제한 2초 문제 링크 접근 과정 1. 다각형의 면적?, CCW CCW(벡터의 외적)은 두 벡터가 이루는 평행사변형의 넓이를 계산합니다. 만약 오목한 부분이 있다면? 그 부분에 대해서는 CCW 결과가 부...

2019년 7월 14일
·
0개의 댓글

[기하] CCW

1. CCW 란 CCW (Counter Clock Wise, 원래 의미는 시계 반대방향) 는 3개의 점 r, p, q가 있을때 벡터 rp를 기준으로 점 q가 어느 위치(왼쪽, 같은 직선, 오른쪽)에 있는지를 판별하는 방법입니다. 벡터의 외적입니다. 외적은 교환법칙이 성립하지 않습니다. AB 와 BA가 같지 않습니다. 기하 알고리즘의 가장 기본 개념입니다. ...

2019년 7월 14일
·
0개의 댓글
post-thumbnail

백준 1688 지민이의 테러 (레이 캐스팅 알고리즘, 다각형 내부 외부 판별)

문제 n개의 정점이 주어집니다. 3개의 줄에 좌표가 주어집니다. 3개의 줄에 주어진 각각의 좌표가 n개의 정점으로 구성된 다각형 내부에 있는지 외부에 있는지 판별하세요 n (1 ≤ n ≤ 1만) 정점의 수 1만 이하 좌표의 크기 10억이하 사용한 알고리즘 CCW, 선분교차 시간 제한 2초 문제 링크 접근 과정 1. 다각형의 내부, 외부 판별 한점이 다각형...

2019년 7월 12일
·
2개의 댓글