시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 1269 | 432 | 365 | 38.462% |
지구이는 std::sort에 무한한 신뢰를 가지고 있다. 빠른 정렬 알고리즘을 직접 구현하기 위해서는 적어도 20줄 넘게 코딩해야 하지만, std::sort는 한 줄이면 끝나기 때문이다. 구조체 배열에 쓰기 위해서는 부등호 연산을 정의하는 등의 추가 구현이 필요하지만, 그 정도의 단점은 직접 구현해야하는 것에 비하면 아무것도 아니었다.
그런 이유에서 S.M.T를 매일 외치며 코딩을 하는 지구이는 어느 날 이유를 알 수 없는 “틀렸습니다”를 받게 되었다. 문제는 매우 간단하다.
“평면의 x ≥ 0, y ≥ 0 부분에 점 N개가 있다. 이 점들을 다음과 같은 조건을 만족하도록 정렬하시오. 모든 i < j에 대해, i번째 점 (xi, yi)와 j번째 점 (xj, yj)는 xi * yj ≤ xj * yi 를 만족한다.”
지구이는 문제의 조건을 오퍼레이터로 정의하여 std::sort로 정렬했지만, 틀리고 말았다. 코드에 std::sort밖에 없는데도 계속 틀리는 지구이는 데이터를 열심히 넣어봤지만, 결국 반례데이터를 찾지 못했다.
지구이를 도와 코드의 반례데이터를 찾아주자!
지구이의 코드는 여기에 있다.
입력은 없다.
첫 번째 줄에 점의 개수 N (2 ≤ N ≤ 1000)을 출력한다.
두 번째 줄부터 N개의 줄에 x좌표, y좌표를 각각 출력한다. (0 ≤ x ≤ 1000, 0 ≤ y ≤ 1000)
2 1 0 0 1
채점 서버는 libstdc++를 사용하여 지구이의 코드를 컴파일했다.