Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- typedef long double ld;
- struct pt{
- ld x,y;
- pt(){};
- pt(ld xx, ld yy){x=xx,y=yy;}
- bool operator < (const pt & o){
- if(x != o.x) return x < o.x;
- return y < o.y;
- }
- };
- ///////////////////////////////////
- int n;
- const double EPS = 1e-10;
- vector<pt> arr;
- ///////////////////////////////////
- ld dist(pt a){
- return sqrtl(a.x * a.x + a.y*a.y);
- }
- ld distsqr(pt a){
- return a.x * a.x + a.y * a.y;
- }
- ld dist(pt a, pt b){
- return dist(pt(a.x - b.x, a.y - b.y));
- }
- ld distsqr(pt a, pt b){
- return distsqr(pt(a.x - b.x, a.y - b.y));
- }
- ld cw(pt a, pt b){
- return a.x * b.y - a.y * b.x;
- }
- pair<pt, ld> getCircleByThree(pt A, pt B, pt C){
- vector<pt> v = {A,B,C};
- sort(v.begin(),v.end());
- A = v[0];
- B = v[1];
- C = v[2];
- pt AB = pt(B.x - A.x, B.y - A.y);
- pt BC = pt(C.x - B.x, C.y - B.x);
- pt CA = pt(A.x - C.x, A.y - C.y);
- ld a = dist(B,C);
- ld b = dist(A,C);
- ld c = dist(A,B);
- ld S = abs(cw(AB, CA))/2;
- if(S<EPS){
- ld R = dist(A,C)/2;
- return {pt((A.x+C.x)/2, (A.y + C.y)/2), R};
- }
- ld R = a * b * c / 4 / S;
- ld phi = acos(c / 2 / R);
- phi = M_PI * 2 - phi;
- pt ABR = pt(AB.x/c*R, AB.y/c*R);
- pt AO = pt(ABR.x * cos(phi) - ABR.y * sin(phi),
- ABR.y * cos(phi) + ABR.x * sin(phi));
- pt O = pt(A.x + AO.x, A.y + AO.y);
- return {O, R};
- }
- bool in_circle(pt a, pt o, ld r){
- return distsqr(a,o) <= r*r + EPS;
- }
- pair<pt, ld> trivial(vector<pt> B){
- if(B.size()==0)
- return {pt(-1e9,-1e9), 0};
- if(B.size()==1)
- return {B[0], 0};
- if(B.size()==3)
- return getCircleByThree(B[0],B[1],B[2]);
- ld R = dist(B[0], B[1])/2;
- pt O = pt((B[0].x + B[1].x)/2,(B[0].y + B[1].y)/2);
- return {O,R};
- }
- pair<pt, ld> welzl(vector<pt> & P, vector<pt> R){
- if(R.size() == 3 || P.size() == 0){
- return trivial(R);
- }
- pt p = P.back();
- P.pop_back();
- auto D = welzl(P, R);
- if(in_circle(p, D.first, D.second)){
- P.push_back(p);
- return D;
- }
- R.push_back(p);
- auto ans = welzl(P,R);
- P.push_back(p);
- return ans;
- }
- int main(){
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- cin>>n;
- for(int i=0;i<n;i++){
- pt nxt;
- cin>>nxt.x>>nxt.y;
- arr.push_back(nxt);
- }
- random_shuffle(arr.begin(),arr.end());
- auto ans = welzl(arr, {});
- cout<<fixed<<setprecision(25)<<ans.first.x<<" "<<ans.first.y<<endl<<ans.second<<endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement