Advertisement
999ms

Untitled

Mar 13th, 2019
217
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.37 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. typedef long double ld;
  5.  
  6. struct pt{
  7.     ld x,y;
  8.     pt(){};
  9.     pt(ld xx, ld yy){x=xx,y=yy;}
  10.     bool operator < (const pt & o){
  11.         if(x != o.x) return x < o.x;
  12.         return y < o.y;
  13.     }
  14. };
  15.  
  16. ///////////////////////////////////
  17.  
  18. int n;
  19. const double EPS = 1e-10;
  20. vector<pt> arr;
  21.  
  22. ///////////////////////////////////
  23.  
  24. ld dist(pt a){
  25.     return sqrtl(a.x * a.x + a.y*a.y);
  26. }
  27. ld distsqr(pt a){
  28.     return a.x * a.x + a.y * a.y;
  29. }
  30. ld dist(pt a, pt b){
  31.     return dist(pt(a.x - b.x, a.y - b.y));
  32. }
  33. ld distsqr(pt a, pt b){
  34.     return distsqr(pt(a.x - b.x, a.y - b.y));
  35. }
  36. ld cw(pt a, pt b){
  37.     return a.x * b.y - a.y * b.x;
  38. }
  39. pair<pt, ld> getCircleByThree(pt A, pt B, pt C){
  40.     vector<pt> v = {A,B,C};
  41.     sort(v.begin(),v.end());
  42.     A = v[0];
  43.     B = v[1];
  44.     C = v[2];
  45.     pt AB = pt(B.x - A.x, B.y - A.y);
  46.     pt BC = pt(C.x - B.x, C.y - B.x);
  47.     pt CA = pt(A.x - C.x, A.y - C.y);
  48.     ld a = dist(B,C);
  49.     ld b = dist(A,C);
  50.     ld c = dist(A,B);
  51.     ld S = abs(cw(AB, CA))/2;
  52.     if(S<EPS){
  53.         ld R = dist(A,C)/2;
  54.         return {pt((A.x+C.x)/2, (A.y + C.y)/2), R};
  55.     }
  56.     ld R = a * b * c / 4 / S;
  57.     ld phi = acos(c / 2 / R);
  58.    
  59.     phi = M_PI * 2 - phi;
  60.     pt ABR = pt(AB.x/c*R, AB.y/c*R);
  61.     pt AO = pt(ABR.x * cos(phi) - ABR.y * sin(phi),
  62.                      ABR.y * cos(phi) + ABR.x * sin(phi));
  63.     pt O = pt(A.x + AO.x, A.y + AO.y);
  64.     return {O, R};
  65. }
  66.  
  67. bool in_circle(pt a, pt o, ld r){
  68.     return distsqr(a,o) <= r*r + EPS;
  69. }
  70.  
  71. pair<pt, ld> trivial(vector<pt> B){
  72.     if(B.size()==0)
  73.         return {pt(-1e9,-1e9), 0};
  74.     if(B.size()==1)
  75.         return {B[0], 0};  
  76.     if(B.size()==3)
  77.         return getCircleByThree(B[0],B[1],B[2]);
  78.     ld R = dist(B[0], B[1])/2;
  79.     pt O = pt((B[0].x + B[1].x)/2,(B[0].y + B[1].y)/2);
  80.     return {O,R};
  81. }
  82.  
  83. pair<pt, ld> welzl(vector<pt> & P, vector<pt> R){
  84.     if(R.size() == 3 || P.size() == 0){
  85.         return trivial(R);
  86.     }
  87.     pt p = P.back();
  88.     P.pop_back();
  89.     auto D = welzl(P, R);
  90.     if(in_circle(p, D.first, D.second)){
  91.         P.push_back(p);
  92.         return D;
  93.     }
  94.     R.push_back(p);
  95.     auto ans = welzl(P,R);
  96.     P.push_back(p);
  97.     return ans;
  98. }
  99.  
  100.  
  101. int main(){
  102.     ios_base::sync_with_stdio(false);
  103.     cin.tie(nullptr);
  104.     cin>>n;
  105.     for(int i=0;i<n;i++){
  106.         pt nxt;
  107.         cin>>nxt.x>>nxt.y;
  108.         arr.push_back(nxt);
  109.     }
  110.    
  111.     random_shuffle(arr.begin(),arr.end());
  112.  
  113.     auto ans = welzl(arr, {});
  114.  
  115.     cout<<fixed<<setprecision(25)<<ans.first.x<<" "<<ans.first.y<<endl<<ans.second<<endl;
  116.  
  117.     return 0;
  118. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement