레이팅 미적용과거에 농부 존은 새로운 소 스포츠에 대한 여러 혁신적인 아이디어를 구상했는데, 그중 하나가 소 떼가 코스를 돌며 장애물을 뛰어넘는 소 장애물 경마(Cow Steeplechase)였다. 이 스포츠에 대한 관심을 끌어모으려던 과거의 노력은 성과가 엇갈렸기에, 그는 더 큰 홍보 효과를 노리고 자신의 농장에 훨씬 더 큰 소 장애물 경마 코스를 지으려 한다.
농부 존의 새 코스는 \(1 \ldots N\)으로 편리하게 번호가 붙은 \(N\)개의 장애물 (\(2 \leq N \leq 10^5\))을 중심으로 세심하게 설계되었으며, 각 장애물은 코스의 2차원 지도 위에서 선분으로 표현된다. 이 선분들은 끝점에서조차 서로 어떤 식으로도 교차해서는 안 된다.
안타깝게도 농부 존은 코스 지도를 만들 때 주의를 기울이지 않았고, 선분들 사이에 교차가 있음을 알아차린다. 하지만 그는 선분을 딱 하나만 제거하면 지도가 원래 의도대로 교차하는 선분이 없는(끝점에서도 교차하지 않는) 상태로 복원된다는 것도 알아차린다.
농부 존이 계획에서 제거하여 어떤 선분도 교차하지 않는 성질을 복원할 수 있는 선분 하나를 구하시오. 이렇게 제거할 수 있는 선분이 여러 개라면, 입력에서 가장 먼저 나오는 것의 번호를 출력한다.
문제 제공: Brian Dean
문제 제공: Brian Dean
첫째 줄에 \(N\)이 주어진다. 남은 \(N\)개의 줄 각각은 네 정수 \(x_1\) \(y_1\) \(x_2\) \(y_2\)로 선분 하나를 나타내며, 모두 \(10^9\) 이하의 음이 아닌 정수이다. 선분의 끝점은 \((x_1, y_1)\)과 \((x_2, y_2)\)이다. 모든 끝점은 서로 다르다.
그 선분을 제거하면 남은 선분들이 교차하지 않게 되는 선분 중, 입력에서 가장 앞선 번호를 출력한다.
cowjump.in · 출력을 쓸 파일 cowjump.out4
2 1 6 1
4 0 1 5
5 6 5 5
2 7 1 32Note: You may want to be careful of integer overflow in this problem, due to the
size of the integers provided as coordinates of segment endpoints.
riseoj 작성
출처 올림피아드 > USACO > 2018-2019 > US Open > Silver