| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 0.5 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 171 | 59 | 54 | 41.221% |
볼록 격자 $N$각형이란, $N$개의 점으로 이루어진 모든 점의 좌표가 정수인 볼록 $N$각형을 의미한다. 여기서 어떤 다각형이 볼록하다는 것은, 모든 내각이 180ドル^\circ$ 미만이며, 다각형을 이루는 임의의 변을 연장해도 그 다각형의 내부를 지나지 않음을 의미한다.
볼록 격자 $N$각형의 $N$개의 점들 중 2ドル$개의 점을 골라 만들 수 있는 선분의 개수는 $M=\binom{N}{2}$개, 3ドル$개 이상의 점을 골라 만들 수 있는 볼록 다각형의 수는 $K=\binom{N}{3} +\binom{N}{4} +\binom{N}{5} +\cdots =2^N-\binom{N}{0} -\binom{N}{1} -\binom{N}{2}$개가 존재한다.
이때, $M$개의 선분의 길이는 모두 무리수이며, $K$개의 볼록 다각형의 넓이는 모두 유리수가 되도록 하는 볼록 격자 $N$각형을 실수로 만든 유리라 부르기로 했다.
$N$이 주어졌을 때, $N$개의 점으로 이루어진 실수로 만든 유리가 있다면 찾아보자.
첫 번째 줄에 정수 $N(1\le N\le 10^4)$이 주어진다.
첫 번째 줄부터 $N$개의 줄에 걸쳐 $N$개의 점으로 이루어진 실수로 만든 유리를 구성하는 점의 좌표 $\left( x,y \right)$을 출력한다. 각 좌표의 범위는 0ドル\le x,y\le 5\times 10^7$을 만족해야 한다.
만약 주어진 범위 내의 정답이 존재하지 않는다면 대신 첫 번째 줄에 -1을 출력한다.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 10 | $N\le 2$ |
| 2 | 30 | $N\le 5,000円$ |
| 3 | 60 | 추가적인 제한 조건 없음 |
2
-1
2ドル$개의 점으로 이루어진 볼록 다각형은 존재하지 않으므로, 2ドル$개의 점으로 이루어진 실수로 만든 유리는 존재하지 않는다.
4
124124 0 690690 814814 814814 124124 0 690690
예제에서 만든 사각형은 아래와 같이 정사각형이고, 6ドル$개의 선분의 길이는 네 개의 2ドル,円 002\sqrt{122,円 869},ドル 두 개의 2ドル,円 002\sqrt{245,円 738}$으로 모두 무리수이며, 5ドル$개의 볼록 다각형의 넓이는 네 개의 246ドル,円 229,円 721,円 738,ドル 한 개의 492ドル,円 459,円 443,円 476$로 모두 유리수이다.
볼록 다각형을 순서대로 출력하지 않아도 됨에 유의하자.
University > 고려대학교 > MatKor Cup > 제6회 고려대학교 MatKor Cup: 2025 Winter 연습 세션 PB번
University > 고려대학교 > MatKor Cup > 제1회 MatKor Cup: 2022 Summer 연습 세션 PC번