시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB176362427.907%

문제

주식회사 슈퍼브에이아이 구성원들은 커피값 내기를 하기 위하여 슈퍼브 다트라는 새로운 게임을 만들었다. 슈퍼브 다트의 규칙은 아래와 같다.

  • 2차원 평면 위에 다트판을 그린다.
  • 다트판은 평면 위의 점들을 정점으로 하고 그 사이를 잇는 선분들을 간선으로 하여 만들어지는 그래프이다.
    • 각 정점은 정수 좌표를 가지며, 좌표가 서로 같은 정점은 없다.
    • 만들어진 그래프는 중복되는 간선을 가지지 않는 단순 그래프이며 모든 임의의 두 정점 사이의 경로가 항상 존재하는 연결 그래프이다.
    • 만들어진 그래프는 서로 다른 선분끼리 교차하지 않으며, 두 선분이 정점을 공유하는 경우 그 점에서만 접할 수 있는 평면 그래프이다.
  • 다트판 위에 다트를 던질 때, 한 번의 시행으로 얻는 점수는 다트가 꽂힌 점이 포함된 영역의 넓이에 반비례한다.
    • 어떤 점을 포함하는 영역이란 그 점에서 다트판의 간선들과 교차하거나 접하지 않는 경로로 연결할 수 있는 점들의 집합이다. 여기서 경로란 그래프상의 경로가 아닌 평면상에서의 경로를 의미하며, 이는 곡선이 될 수도 있다.
    • 넓이가 무한한 곳이나 밖, 혹은 점이나 간선 바로 위에 꽂혔을 경우 이는 영역으로 치지 않으며 0점을 얻게 된다.

호기심이 많은 슈퍼브에이아이 구성원들은 이러한 다트판에서 나올 수 있는 점수들의 조합이 궁금해졌다. 이 궁금증을 해결하기 위해 우선 다트판이 주어졌을 때 다트판에 있는 영역들의 넓이를 계산해보자.

입력

첫 번째 줄에 다트판의 정점 개수와 간선 개수 N, M(1 ≤ N, M ≤ 100,000)이 주어진다. 각 정점에는 1부터 N까지, 각 간선에는 1부터 M까지 순서대로 번호가 붙어 있다.

다음 N개의 줄에는 정점들의 좌표가 주어진다. 이 중 i번째 줄에는 i번 정점의 x좌표 xi와 y좌표 yi(-106xi, yi ≤ 106)가 띄어쓰기로 구분되어 주어진다. 중복된 좌표는 주어지지 않는다.

다음 M개의 줄에는 다트판의 간선이 주어진다. 각 줄은 두 개의 정수 s, e(1 ≤ s, eN)로 이루어져 있으며, 이는 간선의 양 끝 정점 번호를 의미한다. 양 끝점은 서로 다르며, 중복된 간선은 없다. 서로 다른 두 간선은 최대 하나의 교차점을 가지며, 임의의 서로 다른 두 간선이 하나의 교차점을 가진다면 두 간선은 해당 교차점을 양 끝으로 공유한다.

주어진 다트판의 모든 정점은 간선으로 연결되어 있다.

출력

첫 번째 줄에 다트판에 있는 넓이가 0보다 크고 유한한 영역의 개수 S를 출력한다.

다음 S개의 줄에 해당 영역들의 넓이를 오름차순으로 소수점 둘째 자리에서 반올림하여 출력한다.

예제 입력 1

5 6
0 0
0 1
0 3
1 1
1 3
1 2
2 3
1 4
2 4
4 5
3 5

예제 출력 1

2
0.5
2.0

예제 입력 2

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

예제 출력 2

4
4.0
4.0
12.0
16.0

출처

University > 경인지역 6개대학 연합 > shake! 2019 D번