Advertisement
Guest User

Untitled

a guest
Apr 22nd, 2019
94
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.29 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long int ll;
  4. typedef double ld;
  5. typedef vector<ll> vi;
  6. // push_back insert lower_bound upper_bound erase
  7. #define F(a) for ( ll i = 0; i < (ll)(a); ++i )
  8.  
  9. #ifndef M_PI
  10. #define M_PI 3.14159265358979323846264338327950288
  11. #endif//M_PI
  12. #define EPS (1e-10)
  13. #define EQ(a,b) (fabs(a-b) <= fabs(a+b) * EPS)
  14.  
  15. struct Pt{
  16.     ld x,y;
  17.     bool operator <(const Pt &p) const {
  18.         return x < p.x || x == p.x && y < p.y;
  19. //      return x < p.x-EPS || EQ(x,p.x) && y < p.y-EPS);
  20.     }
  21.     Pt operator-(){return{-x,-y};}
  22.     Pt operator+(const Pt&p){return{x+p.x,y+p.y};}
  23.     Pt operator-(const Pt&p){return{x-p.x,y-p.y};}
  24.     Pt operator*(ld d){return {x*d,y*d};}
  25.     Pt operator/(ld d){return {x/d,y/d};}
  26.     friend ostream &operator<<(ostream &os, const Pt&a){
  27.         os<<a.x<<' '<<a.y;
  28.         return os;
  29.     }
  30.     friend istream &operator>>(istream &is, Pt&a){
  31.         is>>a.x>>a.y;
  32.         return is;
  33.     }
  34. };
  35. struct Cir {
  36.     Pt s;
  37.     ld r;
  38.     Pt point(double a)const{return {s.x+cos(a)*r,s.y+sin(a)*r};}
  39.     bool operator<(const Cir& a){
  40.         return r<a.r;
  41.     }
  42. };
  43. // double comparasion
  44. int dcmp(ld x){return (fabs(x)<EPS)?0:(x<0?-1:1); }
  45. // has + sign for left side and - for right side
  46. // equals |a|*|b|*cos(alf)
  47. ld cross(Pt a, Pt b){ return a.x*b.y-a.y*b.x; }
  48. ld cross(Pt a, Pt b, Pt c){ return cross(b-a,c-a); }
  49. // simmilar vector -> + / oposite -> - sign
  50. ld dot(Pt a, Pt b){ return a.x*b.x+a.y*b.y; }
  51. ld norm(Pt a){ return sqrt(dot(a,a)); }
  52. ld points_distance(Pt a, Pt b){ return norm(b-a); }
  53. ld angle(Pt a,Pt b){return acos(dot(a,b)/norm(a)/norm(b));}
  54. // angle of vector v from +x axis
  55. ld angle(Pt v){ return atan2(v.y,v.x); }
  56. // perpendicular vector of unit length
  57. Pt normal(Pt a){ ld n=norm(a); return {-a.y/n,a.x/n}; }
  58. bool operator==(const Pt&a,const Pt&b){return EQ(a.x-b.x,0) && EQ(a.y-b.y,0);}  
  59. bool operator!=(const Pt&a,const Pt&b){return !(a==b);}
  60.  
  61. // circle circle intersection points
  62. ll ccpp(Cir c1,Cir c2){
  63.     ld d=norm(c1.s-c2.s);
  64.     if(EQ(d,0)){
  65.         if(EQ(c1.r-c2.r,0)) return -1; // Two circles coincide
  66.         return 0;
  67.     }
  68.     if(dcmp(c1.r+c2.r-d)<0) return 0;
  69.     if(dcmp(fabs(c1.r-c2.r)-d)>0) return 0;
  70.     ld a=angle(c2.s-c1.s,{1,0});
  71.     ld da=acos((c1.r*c1.r+d*d-c2.r*c2.r)/(2*c1.r*d));
  72.     return 2;
  73. }
  74.  
  75.  
  76. int main() {
  77.     ios::sync_with_stdio(false);
  78.     ll N;cin>>N;
  79.     vector<Cir> circles(N);
  80.     F(N) cin>>circles[i].s>>circles[i].r;
  81.     sort(circles.begin(),circles.end());
  82.     //{
  83.     //    ll total=0;
  84.     //    for(int j=0; j<N; ++j){
  85.     //        for(int k=j+1; k<N; ++k){
  86.     //            ll res=ccpp(circles[j],circles[k]);
  87.     //            //cout<<"inter of "<<j<<" and "<<k<<" is: ";
  88.     //            total+=res;
  89.     //            if(res==2){
  90.     //                cout<<j<<' '<<k<<endl;
  91.     //            //}else{
  92.     //                //cout<<"none"<<endl;
  93.     //            }
  94.     //        }
  95.     //    }
  96.     //    cout<<"total: ";
  97.     //    cout<<total<<endl;
  98.     //}
  99.     ll total=0;
  100.     vector<vi> contains(N);
  101.     set<ll> top;
  102.     for(int j=0; j<N; ++j){
  103.         //cout<<j; for(ll n:top)cout<<' '<<n;cout<<endl;
  104.         unordered_set<ll> done;
  105.         queue<ll> q;
  106.         for(ll n:top){q.push(n);done.insert(n);}
  107.         while(!q.empty()){
  108.             ll t=q.front();q.pop();
  109.             ll r=ccpp(circles[j],circles[t]);
  110.             if(r==0){
  111.                 //cout<<"not: "<<j<<' '<<t<<endl;
  112.                 //cout<<"for "<<j<<' ';
  113.                 //cout<<"contains "<<t<<' ';
  114.                 //cout<<endl;
  115.                 contains[j].push_back(t);
  116.                 top.erase(t);
  117.             }else if(r==2){
  118.                 //cout<<"int: "<<j<<' '<<t<<endl;
  119.                 //cout<<"for "<<j<<' ';
  120.                 //cout<<"not "<<t<<' ';
  121.                 //cout<<endl;
  122.                 for(ll n:contains[t]){
  123.                     if(!done.count(n)){
  124.                         q.push(n);
  125.                         done.insert(n);
  126.                     }
  127.                 }
  128.                 total+=2;
  129.                 if(total>2*N){
  130.                     goto end;
  131.                 }
  132.             }else{
  133.                 assert(false);
  134.             }
  135.         }
  136.         top.insert(j);
  137.     }
  138. end:
  139.     if(total>2*N){
  140.         cout<<"greater"<<endl;
  141.     }else{
  142.         cout<<total<<endl;
  143.     }
  144.  
  145.     return 0;
  146. }//Kepler: Blazewan
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement