BAPC1 BAPC 2005 Preliminaries D - Mandalas Problem Link500개 이하의 원들이 주어지면, 몇 개의 영역으로 나뉘는지를 묻는 문제이다.오일러의 정리에 따르면 V - E + F = 2이고, "위키피디아 - Planar graphs 부분"을 보면 평면그래프에서는 V - E + F - C = 1이라고 한다.따라서 원들의 교차점을 V라 보고, E는 원들로 인해서 나누어지는 호들의 개수, F는 우리가 구하고자 하는 영역의 개수, C는 원들의 component 개수라 보고 풀면 된다.두 원의 교차점들 중, 같은 점들에 대한 중복처리 등을 신경써서 해야한다. epsilon값을 너무 작게 주어도 안되고, 적당히 1e-5 정도로 주어야 맞게 판정된다. 2016. 4. 5. 이전 1 다음