저글링 고군분투: 1부 timer 20s memory 1024MB

이 문제의 처음 두 문단(이 문단은 제외)과 "Juggle Struggle: Part 2"의 처음 두 문단은 동일하다. 그 외의 내용은 서로 독립적이며, 한 문제를 읽거나 풀기 위해 다른 문제를 읽거나 풀 필요는 없다.

Graceful Chainsaw Jugglers 그룹의 매니저인 당신은 쇼를 좀 더 흥미롭게 만들기로 했다. 각 저글러가 자기 전기톱을 혼자 저글링하는 대신, 저글러들을 쌍으로 묶어 각 쌍이 전기톱을 서로 던지며 주고받게 하고 싶다. 이 새로운 공연에서는 2 × N명의 저글러가 동시에 무대에 올라, N개의 쌍을 이루며, 각 저글러는 정확히 하나의 쌍에 속한다.

서로 다른 쌍들이 저글링하는 전기톱이 충돌할 위험이 있다면 쇼가 더 인상적일 것이라고 생각한다. 무대를 2차원 평면이라고 하고, 한 쌍을 이루는 두 저글러의 위치를 잇는 평면 위의 선분을 그 쌍의 저글링 경로(juggling path)라고 하자. 두 저글링 경로가 교차하면, 그 두 쌍이 저글링하는 전기톱은 충돌 위험이 있다고 말한다. 저글러들의 공간상의 위치와 쌍짓기를 합쳐서 배치(arrangement)라고 부른다. 어떤 배치가 훌륭하다(magnificent)는 것은, 임의의 두 쌍이 저글링하는 전기톱이 모두 충돌 위험이 있다는 뜻이다.

많은 고민과 설계 끝에 당신은 훌륭한 배치를 하나 만들어냈다. 무대 위 저글러들의 위치와 쌍짓기를 종이에 적어 두었는데, 불행히도 잘못 던져진 전기톱이 종이를 반으로 잘라 버려 쌍짓기가 적힌 쪽을 잃어버렸다. 무대 장식은 저글러들의 위치를 기반으로 이미 설계되어 있으므로, 그 위치들은 바꿀 수 없다. 공연의 대망의 첫 무대가 몇 시간 남지 않았으니, 작동하는 훌륭한 배치를 찾아야 한다! 2차원 무대 위의 각 저글러의 위치가 주어질 때, 훌륭한 배치가 되도록 저글러들을 쌍으로 묶는 방법을 찾아라.