전체태그 보기

#기하알고리즘 (3개의 포스트)

백준 2166 다각형의 면적
skyepodium

백준 2166 다각형의 면적

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

[기하] CCW

2019년 7월 14일0개의 댓글
1. CCW 란 - CCW (Counter Clock Wise, 원래 의미는 시계 반대방향) 는 3개의 점 r, p, q가 있을때 벡터 rp를 기준으로 점 q가 어느 위치(왼쪽, 같은 직선, 오른쪽)에 있는지를 판별하는 방법입니다. - 벡터의 외적입니다. - 외적은 교환법칙이 성립하지 않습니다. AB 와 BA가 같지 않습니다. - 기하 알고리즘의 가장 기본...
백준 1688 지민이의 테러 (레이 캐스팅 알고리즘, 다각형 내부 외부 판별)
skyepodium
문제 - n개의 정점이 주어집니다. - 3개의 줄에 좌표가 주어집니다. - 3개의 줄에 주어진 각각의 좌표가 n개의 정점으로 구성된 다각형 내부에 있는지 외부에 있는지 판별하세요 - n (1 ≤ n ≤ 1만) 정점의 수 1만 이하 - 좌표의 크기 10억이하 - 사용한 알고리즘 CCW, 선분교차 - 시간 제한 2초 - 문제 링크 - 접근 과정 ...