백준 2389 세상의 중심에서... C++ / Welzl algorithm
https://www.acmicpc.net/problem/2389 최대 100개의 점을 모두 포함하는 원의 중심과 반지름을 구하는 문제입니다. 2차원에서 원은 3개의 점으로 구할 수 있습니다. 2개의 점을 지나는 최소 원은 선분을 지름으로 하는 원입니다. (이와 같은 논리로 d차원에서는 affine independent한 d+1개의 점이 있으면, 그 점을 지나는 boundary는 유일하게 결정됩니다.)(참고 : https://freshrimpsushi.github.io/ko/posts/2385/) 100개의 점을 대상으로 100C1, 100C2, 100C3 케이스에 대해 원을 구성하고, 100개의 점들과 포함유무를 확인하는 브루트포스 방식도 가능합니다. (대충 복잡도 계산해보면 1600만 정도 돌아야 함..
알고리즘/백준
2025. 3. 9. 23:31