슈퍼브 다트

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

• 2차원 평면 위에 다트판을 그린다.

• 다트판은 평면 위의 점들을 정점으로 하고 그 사이를 잇는 선분들을 간선으로 하여 만들어지는 그래프이다.

  • 각 정점은 정수 좌표를 가지며, 좌표가 서로 같은 정점은 없다.
  • 만들어진 그래프는 중복되는 간선을 가지지 않는 단순 그래프이며 모든 임의의 두 정점 사이의 경로가 항상 존재하는 연결 그래프이다.
  • 만들어진 그래프는 서로 다른 선분끼리 교차하지 않으며, 두 선분이 정점을 공유하는 경우 그 점에서만 접할 수 있는 평면 그래프이다.

• 다트판 위에 다트를 던질 때, 한 번의 시행으로 얻는 점수는 다트가 꽂힌 점이 포함된 영역의 넓이에 반비례한다.

  • 어떤 점을 포함하는 영역이란 그 점에서 다트판의 간선들과 교차하거나 접하지 않는 경로로 연결할 수 있는 점들의 집합이다. 여기서 경로란 그래프상의 경로가 아닌 평면상에서의 경로를 의미하며, 이는 곡선이 될 수도 있다.
  • 넓이가 무한한 곳이나 밖, 혹은 점이나 간선 바로 위에 꽂혔을 경우 이는 영역으로 치지 않으며 0점을 얻게 된다.

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

첫 번째 줄에 다트판의 정점 개수와 간선 개수 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개의 줄에 해당 영역들의 넓이를 오름차순으로 소수점 둘째 자리에서 반올림하여 출력한다.