계산 기하학

[백준 1708] 볼록 껍질 C++

1708번: 볼록 껍질 첫째 줄에 점의 개수 N(3 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 점의 x좌표와 y좌표가 빈 칸을 사이에 두고 주어진다. 주어지는 모든 점의 좌표는 다르다. x좌표와 y좌표의 범 www.acmicpc.net Convex hull jarvis march와 graham scan 알고리즘은 그림도 없고, 설명도 많이 부족하니 다른 분들의 글을 참고해주세요 코드는 determinant를 사용한 풀이입니다 1. 문제 해결 아이디어 Convex hull 문제를 해결하기 위한 대표적인 2가지 알고리즘에는 Jarvis march(gift wrapping) 알고리즘 Graham scan 알고리즘 위 2개가 있다. Jarvis march(gift wrapping)..

[백준 17387] 선분 교차 2 C++

17387번: 선분 교차 2 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. www.acmicpc.net 선분 교차 알고리즘 계산 기하학 알고리즘 중 선분 교차 알고리즘을 공부했다. 1. 문제 해결 아이디어 먼저 두 선분이 교차하는 경우를 알아보자 l1선분의 p1, p2벡터에서 l2선분의 p1으로의 방향과 p1, p2벡터에서 l2선분의 p2로의 방향이 서로 다르다면(한 점이 선분에 포함된 경우 포함) 반드시 두 선분은 교차한다. 두 선분의 직선의 방정식을 구해서 교차하는 한 점을 구하면 선분이 교차하는지 알 수 있지 않을까요? 알 수 없다 아래 두 선분을 보자 l2선분을 직선으로 만들면 l1과 교차하게된다. 하지만 l1과 l2..