Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long int ll;
- typedef double ld;
- typedef vector<ll> vi;
- // push_back insert lower_bound upper_bound erase
- #define F(a) for ( ll i = 0; i < (ll)(a); ++i )
- #ifndef M_PI
- #define M_PI 3.14159265358979323846264338327950288
- #endif//M_PI
- #define EPS (1e-10)
- #define EQ(a,b) (fabs(a-b) <= fabs(a+b) * EPS)
- struct Pt{
- ld x,y;
- bool operator <(const Pt &p) const {
- return x < p.x || x == p.x && y < p.y;
- // return x < p.x-EPS || EQ(x,p.x) && y < p.y-EPS);
- }
- Pt operator-(){return{-x,-y};}
- Pt operator+(const Pt&p){return{x+p.x,y+p.y};}
- Pt operator-(const Pt&p){return{x-p.x,y-p.y};}
- Pt operator*(ld d){return {x*d,y*d};}
- Pt operator/(ld d){return {x/d,y/d};}
- friend ostream &operator<<(ostream &os, const Pt&a){
- os<<a.x<<' '<<a.y;
- return os;
- }
- friend istream &operator>>(istream &is, Pt&a){
- is>>a.x>>a.y;
- return is;
- }
- };
- struct Cir {
- Pt s;
- ld r;
- Pt point(double a)const{return {s.x+cos(a)*r,s.y+sin(a)*r};}
- bool operator<(const Cir& a){
- return r<a.r;
- }
- };
- // double comparasion
- int dcmp(ld x){return (fabs(x)<EPS)?0:(x<0?-1:1); }
- // has + sign for left side and - for right side
- // equals |a|*|b|*cos(alf)
- ld cross(Pt a, Pt b){ return a.x*b.y-a.y*b.x; }
- ld cross(Pt a, Pt b, Pt c){ return cross(b-a,c-a); }
- // simmilar vector -> + / oposite -> - sign
- ld dot(Pt a, Pt b){ return a.x*b.x+a.y*b.y; }
- ld norm(Pt a){ return sqrt(dot(a,a)); }
- ld points_distance(Pt a, Pt b){ return norm(b-a); }
- ld angle(Pt a,Pt b){return acos(dot(a,b)/norm(a)/norm(b));}
- // angle of vector v from +x axis
- ld angle(Pt v){ return atan2(v.y,v.x); }
- // perpendicular vector of unit length
- Pt normal(Pt a){ ld n=norm(a); return {-a.y/n,a.x/n}; }
- bool operator==(const Pt&a,const Pt&b){return EQ(a.x-b.x,0) && EQ(a.y-b.y,0);}
- bool operator!=(const Pt&a,const Pt&b){return !(a==b);}
- // circle circle intersection points
- ll ccpp(Cir c1,Cir c2){
- ld d=norm(c1.s-c2.s);
- if(EQ(d,0)){
- if(EQ(c1.r-c2.r,0)) return -1; // Two circles coincide
- return 0;
- }
- if(dcmp(c1.r+c2.r-d)<0) return 0;
- if(dcmp(fabs(c1.r-c2.r)-d)>0) return 0;
- ld a=angle(c2.s-c1.s,{1,0});
- ld da=acos((c1.r*c1.r+d*d-c2.r*c2.r)/(2*c1.r*d));
- return 2;
- }
- int main() {
- ios::sync_with_stdio(false);
- ll N;cin>>N;
- vector<Cir> circles(N);
- F(N) cin>>circles[i].s>>circles[i].r;
- sort(circles.begin(),circles.end());
- //{
- // ll total=0;
- // for(int j=0; j<N; ++j){
- // for(int k=j+1; k<N; ++k){
- // ll res=ccpp(circles[j],circles[k]);
- // //cout<<"inter of "<<j<<" and "<<k<<" is: ";
- // total+=res;
- // if(res==2){
- // cout<<j<<' '<<k<<endl;
- // //}else{
- // //cout<<"none"<<endl;
- // }
- // }
- // }
- // cout<<"total: ";
- // cout<<total<<endl;
- //}
- ll total=0;
- vector<vi> contains(N);
- set<ll> top;
- for(int j=0; j<N; ++j){
- //cout<<j; for(ll n:top)cout<<' '<<n;cout<<endl;
- unordered_set<ll> done;
- queue<ll> q;
- for(ll n:top){q.push(n);done.insert(n);}
- while(!q.empty()){
- ll t=q.front();q.pop();
- ll r=ccpp(circles[j],circles[t]);
- if(r==0){
- //cout<<"not: "<<j<<' '<<t<<endl;
- //cout<<"for "<<j<<' ';
- //cout<<"contains "<<t<<' ';
- //cout<<endl;
- contains[j].push_back(t);
- top.erase(t);
- }else if(r==2){
- //cout<<"int: "<<j<<' '<<t<<endl;
- //cout<<"for "<<j<<' ';
- //cout<<"not "<<t<<' ';
- //cout<<endl;
- for(ll n:contains[t]){
- if(!done.count(n)){
- q.push(n);
- done.insert(n);
- }
- }
- total+=2;
- if(total>2*N){
- goto end;
- }
- }else{
- assert(false);
- }
- }
- top.insert(j);
- }
- end:
- if(total>2*N){
- cout<<"greater"<<endl;
- }else{
- cout<<total<<endl;
- }
- return 0;
- }//Kepler: Blazewan
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement