본문 바로가기

선분 교차 판정

 (5)
[Python] 3878번 점 분리 https://www.acmicpc.net/problem/3878 23/10/06  이전에 볼록 껍질 문제를 쭉 푼 적이 있었는데, 그 때 해결 했던 문제 중 하나이다. 흥미로운 문제라고 생각되어 기록으로 남겨보고자 한다. 문제 접근 방식:  문제의 요구 사항은 검은 점과 흰 점을 오직 하나의 직선만으로 서로 분리할 수 있는지 판단하는 것이다. 검은 점끼리를 고무줄로 감싸고, 흰 점끼리를 고무줄로 감쌌을 때, 두 고무줄이 겹치지 않으면 가능하다고 판단했다. 여기서 볼록껍질이라는 말을 사용하지 않은 이유는 고무줄이라는 용어가 더 적합하다고 생각했기 때문이다. 볼록껍질은 고무줄이라는 말을 온전히 대변하지 않는다. 예를 들어, 두 점만 있는 경우 볼록 껍질을 정의하기가 어려운데, 고무줄은 정의할 수 있다. 한..
[Python] 11668번 파이프 청소 https://www.acmicpc.net/problem/11668 24/05/12  기하학 + 그래프 이론 관련 문제이다. 좋은 문제인 것 같아서 풀이를 남겨보려고 한다. 문제 접근 방식:  문제에서 요구하고 있는 바를 정리해보자. 1. 파이프는 수원지와 도시를 잇는다.2. 두 파이프는 서로 교차할 수 있으며, 한 교차점에는 세 파이프가 동시에 교차하지 않는다.3. 교차점에는 이물질이 끼는데, 한 파이프에 로봇을 넣으면 그 파이프의 교차점을 모두 청소해 줌.4. 로봇이 충돌하는 일을 방지하기 위해 교차점에는 오직 하나의 파이프에만 로봇이 있어야 함.5. 어떤 파이프의 부분 집합을 잡아서 동시에 로봇을 투입했을 때, 두 로봇이 충돌하는 일이 없으면서 모든 교차점을 청소할 수 있는지를 판단해야 함.6. 두..
[Python] 10255번 교차점 https://www.acmicpc.net/problem/10255 10255번: 교차점 이제 사각형의 경계선과 선분의 교차점에 관한 간단한 기하 문제를 풀어볼 것이다. 매우 다행히도 사각형은 항상 축에 평행한 형태로만 놓여 있다. 어떤 사각형과 어떤 선분의 교차점은 항상 0 www.acmicpc.net 22/09/22 선분 교차 알고리즘을 조금 응용한 문제로, 약간의 아이디어가 있어야하는 문제이다. 문제 접근 방식: 무작정 선분 교차 알고리즘을 4번 적용하여 문제를 풀어버리면 조금 난감하다. 왜냐하면, 모서리에만 선이 닿는다고 했을 때, 실제로는 선분과 직사각형이 한 점에서만 만나지만, 선분 교차 알고리즘이 만나는 모서리를 포함하는 두 직선에 대해서 모두 실행되기 때문에 두 점에서 만나는 것으로 오해 ..
[Python] 20149번 선분 교차 3 (추후 보강 예정) https://www.acmicpc.net/problem/20149 20149번: 선분 교차 3 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. www.acmicpc.net 22/09/22 선분 교차 2 문제를 풀었다면 거기에 교점을 구하는 코드를 추가로 집어넣음으로써 문제를 풀 수 있다. 문제 접근 방식: 이 문제를 풀기 전에 선분 교차 2 문제를 풀기를 권장한다. 먼저 CCW알고리즘과 이를 응용한 선분 교차 알고리즘을 이해하고 있다는 가정 하에서 서술하겠다. 선분 교차 알고리즘에 관한 글을 추후에 작성한다면 여기에 글을 덧붙일 예정이다. 어떤 선분이 교차하는지 교차하지 않는지 판단을 했다면, 그 교점을 구해야 한다. 그러면..
CCW 알고리즘(CCW Algorithm) 최근에 배우게 된 CCW 알고리즘에 대해 글을 써보고자 한다. CCW 알고리즘이란? Counter-ClockWise의 줄임말로, 직역하면 반시계 방향이라는 뜻임. 세 점 p1, p2, p3가 주어져 있고, 이 세 점을 p1, p2, p3 순서대로 직선으로 이었을 때, 시계방향으로 휘어지는가, 반시계 방향으로 휘어지는가, 혹은 일직선을 이루는가를 판별하는 알고리즘. 방향이 중요하기 때문에 벡터의 개념을 알아야 함. 이 알고리즘을 활용하여 다양한 기하학 알고리즘에 적용할 수 있음. 대표적으로 선분 교차 판정 알고리즘, 볼록 껍질 알고리즘(컨벡스 헐) 등이 있음. 요약된 내용으로만 보아서는 무슨 뜻인지 잘 모를 수도 있을 것이다. 그래서 다음과 같이 그림을 준비했다. 위의 그림처럼 세 점 P1, P2, P3를..

티스토리툴바