[백준 / BOJ][Python] 2162 - 선분 그룹 https://www.acmicpc.net/problem/2162 2162번: 선분 그룹 첫째 줄에 N(1 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N+1번째 줄에는 양 끝점의 좌표가 x1, y1, x2, y2의 순서로 주어진다. 각 좌표의 절댓값은 5,000을 넘지 않으며, 입력되는 좌표 사이에는 빈칸이 하 www.acmicpc.net 문제 풀이 선분 교차 판정 + 유니온 파인드 이용하는 문제. 교차하는 선분들이 있다면 같은 그룹에 속하는 선분이라는 뜻이기에 Union 작업을 실시하면 된다. N ≤ 3,000 이므로 모든 조합을 시도해도 대략 450만 정도의 수가 나온다. 즉, Naive하게 풀이를 진행하면 된다. 추가로, 모든 Union..

[백준 / BOJ][Python] 17387 - 선분 교차 2 https://www.acmicpc.net/problem/17387 17387번: 선분 교차 2 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. www.acmicpc.net 문제 풀이 '17386 - 선분 교차 1' 문제에서 조건이 추가된 문제 (https://dodobow.tistory.com/27). 세 점 또는 네 점이 모두 한 직선 위에 있는 경우도 있기에, 해당 케이스에 대한 예외 처리를 추가하면 된다. 코드 import sys input = sys.stdin.readline def ccw(p1, p2, p3): #CCW x1, y1 = p1 x2, y2 ..

[백준 / BOJ][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에 대해서는 나중에 알고리즘 부분에서 설명하기로.. 외적을 이용한 CCW가 아니라 좌표를 이용해 기울기를 구하고, 이를 통해 직선의 방정식을 세워 교차 여부를 판단할 수 있지만 소수점 오차로 인해 틀릴 확률이 높다. 그러므로 그냥 마음 편히 CCW를 사용한 풀이를 권장한다. 본인도 직선의 방정식 풀이로 이..