dh_0e

2022 UCPC 예선 B번, 그리디로 풀 수 있는 선분 교차 판정 문제로, N  해결 방법 가중치를 기준으로 정렬한 뒤 가중치가 낮은 베기부터 ccw 알고리즘으로 교차되는 선분의 개수를 구하여 가중치에 곱한 값을 모두 더하여 답을 도출했다. [알고리즘] CCW(Counter Clockwise) 알고리즘CCW 알고리즘CCW(Counter Clockwise)는 세 점의 방향 관계를 판별하는 알고리즘이다.주로 기하학적 문제에서 사용되며, 점 A, B, C가 있을 때 이 세 점이 시계 방향으로 배열되어 있는지, 반 시계 방향으dh-0e.tistory.com #include #include #include using namespace std;typedef long long ll;struct Point { ..

CCW 알고리즘CCW(Counter Clockwise)는 세 점의 방향 관계를 판별하는 알고리즘이다.주로 기하학적 문제에서 사용되며, 점 A, B, C가 있을 때 이 세 점이 시계 방향으로 배열되어 있는지, 반 시계 방향으로 배열되어 있는지를 판단한다.이를 통해 다각형의 내부에 점이 있는지, 선분이 교차하는지 등을 판별할 수 있다.원리벡터의 외적(cross product)을 이용하여 세 점의 방향을 결정한다.점 A, B, C의 좌표를 (Ax, Ay), (Bx, By), (Cx, Cy)라 할 때, 다음과 같은 수식을 사용한다.CCW 값 = (Bx - Ax) * (Cy - Ay) - (By - Ay) * (Cx - Ax)CCW 값 > 0: 점 A, B, C가 반시계 방향으로 배열되어 있음CCW 값 CCW 값..