| 1 | #include "circles.cpp" |
| 2 | vector<point> wP, wR; |
| 3 | pair<point,double> welzl() { |
| 4 | if (wP.empty() || wR.size() == 3) { |
| 5 | if (wR.empty()) return make_pair(point(), 0); |
| 6 | if (wR.size() == 1) return make_pair(wR[0], 0); |
| 7 | if (wR.size() == 2) return make_pair((wR[0]+wR[1])/2.0, |
| 8 | abs(wR[0]-wR[1])/2); |
| 9 | if (abs(cross(wR[1]-wR[0], wR[2]-wR[0])) < EPS) { |
| 10 | point res; double mx = -INFINITY, d; |
| 11 | rep(i,0,3) rep(j,i+1,3) |
| 12 | if ((d = abs(wR[i] - wR[j])) > mx) |
| 13 | mx = d, res = (wR[i] + wR[j]) / 2.0; |
| 14 | return make_pair(res, mx/2.0); } |
| 15 | return circumcircle(wR[0], wR[1], wR[2]); } |
| 16 | swap(wP[rng() % wP.size()], wP.back()); |
| 17 | point res = wP.back(); wP.pop_back(); |
| 18 | pair<point,double> D = welzl(); |
| 19 | if (abs(res - D.first) > D.second + EPS) { |
| 20 | wR.push_back(res); D = welzl(); wR.pop_back(); |
| 21 | } wP.push_back(res); return D; } |
| 22 | // vim: cc=60 ts=2 sts=2 sw=2: |