레야몬

1. 문제 N개의 선분들이 2차원 평면상에 주어져 있다. 두 선분이 서로 만나는 경우에 두 선분은 같은 그룹에 속했다고 하며 그룹의 크기는 그 그룹에 속한 선분의 개수로 정의한다. 이 N개의 선분들은 몇 개의 그룹으로 되어있을까? 또, 가장 큰 그룹에 속하는 선분의 개수는 몇 개인가? - 1 - \(N(1 \leq N \leq 3,000)\) - N개의 줄 - 선분의 양 끝점의 좌표 \(\left|x_{i} \right|, \left|y_{i} \right| \leq 5,000\) - 1 - 그룹의 수 - 2 - 가장 크기가 큰 그룹에 속한 선분의 개수 2. 재정의 선분 그룹 개수와 그 크기 구하기 3. 해결 방법 N*N = 9,000,000으로 CCW를 이용해 선분 교차를 모두 파악하고 이를 union..

1. 문제 2차원 좌표 평면 위 두 선분 \(L_{1}, L_{2}\)가 주어졌을 때 두 선분의 교차 여부를 판단하자. 한 선분의 각 점이 다른 선분이나 끝 점 위에 있는 것도 교차하는 것이다. - 1 - \(x_{1}, y_{1}, x_{2}, y_{2}\) - 2 - \(x_{3}, y_{3}, x_{4}, y_{4}\) \((-1,000,000 \leq x_{i}, y_{i} \leq 1,000,000), (x_{i}, y_{i} \in \mathbb{Z}), (0 < l_{1}, l_{2})\) - 1 - 교차하면 1, 아니면 0을 출력 - 2 - 교차하는 점의 x좌표와 y좌표 출력 2. 재정의 교차점 구하기 3. 해결 방법 CCW로 적절히 하면 되는데 너무 조건 분기가 많아서 생략하고 아래 링크..

먼저 이를 이해하려면 행렬과 백터를 알고 있어야 되는데.... https://jordano-jackson.tistory.com/27 [Algorithm] 선분교차(Line-segment intersection) 판정 알고리즘 • Line-segment intersection 판별 알고리즘의 필요성 Line-segment의 교차 판정은 PS에서 흔히 다뤄지는 문제이다. 예컨대 네 점 이 주어졌다고 하자. 이 때 다음과 같은 두 선분을 생각할 수 있다. 이때 두 jordano-jackson.tistory.com 여기에 알고리즘이 자세히 적혀있다. 많은 조건 분기라는 알고리즘이 있어서 찾아봤는데 아무것도 안나와서 뭐지 했는데 풀어보면서 알았다. 선분의 케이스가 많아서 모두다 고려해야 됬던 거다. 케이스를 다 ..