BAPC 2005 Preliminaries D - Mandalas

Problem Link

500개 이하의 원들이 주어지면, 몇 개의 영역으로 나뉘는지를 묻는 문제이다.

오일러의 정리에 따르면 V - E + F = 2이고, "위키피디아 - Planar graphs 부분"을 보면 평면그래프에서는 V - E + F - C = 1이라고 한다.

따라서 원들의 교차점을 V라 보고, E는 원들로 인해서 나누어지는 호들의 개수, F는 우리가 구하고자 하는 영역의 개수, C는 원들의 component 개수라 보고 풀면 된다.

두 원의 교차점들 중, 같은 점들에 대한 중복처리 등을 신경써서 해야한다. epsilon값을 너무 작게 주어도 안되고, 적당히 1e-5 정도로 주어야 맞게 판정된다.