시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 176 | 36 | 24 | 27.907% |
주식회사 슈퍼브에이아이 구성원들은 커피값 내기를 하기 위하여 슈퍼브 다트라는 새로운 게임을 만들었다. 슈퍼브 다트의 규칙은 아래와 같다.
호기심이 많은 슈퍼브에이아이 구성원들은 이러한 다트판에서 나올 수 있는 점수들의 조합이 궁금해졌다. 이 궁금증을 해결하기 위해 우선 다트판이 주어졌을 때 다트판에 있는 영역들의 넓이를 계산해보자.
첫 번째 줄에 다트판의 정점 개수와 간선 개수 N, M(1 ≤ N, M ≤ 100,000)이 주어진다. 각 정점에는 1부터 N까지, 각 간선에는 1부터 M까지 순서대로 번호가 붙어 있다.
다음 N개의 줄에는 정점들의 좌표가 주어진다. 이 중 i번째 줄에는 i번 정점의 x좌표 xi와 y좌표 yi(-106 ≤ xi, yi ≤ 106)가 띄어쓰기로 구분되어 주어진다. 중복된 좌표는 주어지지 않는다.
다음 M개의 줄에는 다트판의 간선이 주어진다. 각 줄은 두 개의 정수 s, e(1 ≤ s, e ≤ N)로 이루어져 있으며, 이는 간선의 양 끝 정점 번호를 의미한다. 양 끝점은 서로 다르며, 중복된 간선은 없다. 서로 다른 두 간선은 최대 하나의 교차점을 가지며, 임의의 서로 다른 두 간선이 하나의 교차점을 가진다면 두 간선은 해당 교차점을 양 끝으로 공유한다.
주어진 다트판의 모든 정점은 간선으로 연결되어 있다.
첫 번째 줄에 다트판에 있는 넓이가 0보다 크고 유한한 영역의 개수 S를 출력한다.
다음 S개의 줄에 해당 영역들의 넓이를 오름차순으로 소수점 둘째 자리에서 반올림하여 출력한다.
5 6 0 0 0 1 0 3 1 1 1 3 1 2 2 3 1 4 2 4 4 5 3 5
2 0.5 2.0
10 13 2 0 6 4 8 6 2 6 4 2 8 2 0 2 10 2 12 2 12 6 3 2 1 7 10 8 3 6 5 6 2 6 9 10 4 7 6 8 8 9 4 5 1 5 3 4
4 4.0 4.0 12.0 16.0
University > 경인지역 6개대학 연합 > shake! 2019 D번