본문 바로가기
728x90

ccw3

[python] 백준 20149 선분 교차 3 https://www.acmicpc.net/problem/20149   문제 해결선분이 겹치는지 안겹치는지 확인할 때는 CCW (Counter Clock Wise)를 사용한다.선분 1, 선분 2가 있으면 선분 1과 선분 2의 끝점 각각을 CCW를 사용했을 때 부호가 반대로 나오고 선분1의 두 끝점과 선분2를 CCW를 사용했을 때 부호가 반대로 나오면 무조건 두 선분은 만나게 된다.문제는 끝점이 교차할 때 CCW가 0이 나올 경우가 있는데 조건을 나누어 코드를 짜야한다.선분 1의 끝점 두개와 선분 2의 끝점을 보고 선분 1에서 x축 값이 큰 값 (x 같으면 y값)이 선분 1의 x축 값이 작은 값(x같으면 y값)보다 크고 선분 2의 작은값보다 크고 큰값보다 작으면 겹친다. (코드 참고...) CODEimpo.. 2024. 6. 16.
[python] 백준 17386 선분 교차 1 https://www.acmicpc.net/problem/17386 17386번: 선분 교차 1 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. 세 점이 일직선 위에 있는 경우는 없다. www.acmicpc.net 문제 해결 CCW를 사용하는 문제 CCW는 외적을 이야기 한다. 우선 두 직선이 일직선 위에 있는 경우가 없으므로 평행하거나 일치, 여러점이 겹치는 것을 생각할 필요가 없다. 따라서 L2의 끝 두점 (x3,y3), (x4,y4)와 L1의 두 끝점 (x1,y1), (x2,y2)을 CCW로 계산해서 양수가 하나라도 나오면 교차를 하지 않는다. CODE import sys input = sys.stdin.readline .. 2023. 8. 25.
[python] 백준 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 문제 해결 CCW(Counter-Clockwise)를 알면 쉬운 문제. 외적과 관련되어있는데 외적에서 절대값을 없앤 $(X_{1}Y_{2}+X_{2}Y_{3}+X_{3}Y_{1})-(X_{2}Y_{1}+X_{3}Y_{2}+X_{1}Y_{3})$의 부호에 따라 벡터가 움직이는 방향이 다르다는 것이다. $(X_{1}Y_{2}+X_{2.. 2023. 6. 14.
728x90