'ccw' 태그의 글 목록

백준 2166. 다각형의 면적

https://www.acmicpc.net/problem/2166 2166번: 다각형의 면적 첫째 줄에 N이 주어진다. 다음 N개의 줄에는 다각형을 이루는 순서대로 N개의 점의 x, y좌표가 주어진다. 좌표값은 절댓값이 100,000을 넘지 않는 정수이다. www.acmicpc.net 마찬가지로 CCW 를 이용하는 문제다. CCW 결과로 나오는 외적은 결국 두 벡터가 이루는 평행사변형의 넓이이므로 /2를 해주면 삼각형의 넓이다. 하나의 점을 기준으로 삼각형들로 나눠서 삼각형들의 넓이들을 합해주면 된다. 라고 단순하게 생각하고 제출했는데 계속 오답판정을 받았다. 틀린 코드는 CCW 결과로 음수가 될수 있으므로 음수일 경우 양수로 바꾼후 리턴하도록 했는데, 이 경우 다각형에 오목한 부분이 있을 경우가 계산이..

PS 2022. 2. 24. 21:54

백준 17386. 선분 교차 1

https://www.acmicpc.net/problem/17386 17386번: 선분 교차 1 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. 세 점이 일직선 위에 있는 경우는 없다. www.acmicpc.net CCW 알고리즘을 이용. 이번에는 두 선분의 시작점과 끝점이 주어진다. 선분1이 AB고 선분2가 CD 라고 하면 CCW로 ABC의 방향을 구하고, ABD의 방향을 구한다. 두 방향이 서로 다르다면 교차한다. 하나의 선분 입장에서 다른 선분이 교차한다는 것은 다른 선분의 한쪽 끝점은 좌측에, 한쪽 끝점은 우측에 있다는 것이다. 예를들어 선분 AB기준으로 C가 좌측(반시계 방향)에 있고, D는 우측(시계 방향)에 있다면..

PS 2022. 2. 24. 17:21

백준 11758. CCW

https://www.acmicpc.net/problem/11758 11758번: CCW 첫째 줄에 P1의 (x1, y1), 둘째 줄에 P2의 (x2, y2), 셋째 줄에 P3의 (x3, y3)가 주어진다. (-10,000 ≤ x1, y1, x2, y2, x3, y3 ≤ 10,000) 모든 좌표는 정수이다. P1, P2, P3의 좌표는 서로 다르다. www.acmicpc.net 처음에는 1번점과 2번점으로 직선의 방정식을 구하고, 3번점의 x좌표를 대입했을때의 y값이 주어진 3번점의 y값과 같다면 평행, 위에 있다면 반시계, 아래있다면 시계 이런식으로 판단해봤다. 이 방법은 기울기를 구할때 나누기 연산이 수행되 부동소수점 오차 때문에 실패했다. 앱실론을 정하고 오차 비교도 해봤는데 여전히 실패. 다음 방..

PS 2022. 2. 24. 16:30