平面图欧拉定理的应用
#include <cstdio> #include <iostream> #include <algorithm> #include <cmath> #include <vector> using namespace std; typedef double ld; const ld eps=1e-7; struct Point{ ld x,y; Point(){} Point(ld _x,ld _y):x(_x),y(_y){} friend bool operator <(Point a,Point b){ return a.x+eps<b.x || (fabs(a.x-b.x)<eps && a.y+eps<b.y); } friend bool operator ==(Point a,Point b){ return fabs(a.x-b.x)<eps && fabs(a.y-b.y)<eps; } friend Point operator +(Point a,Point b){ return Point(a.x+b.x,a.y+b.y); } friend Point operator -(Point a,Point b){ return Point(a.x-b.x,a.y-b.y); } friend Point operator *(Point a,ld b){ return Point(a.x*b,a.y*b); } friend Point operator *(ld b,Point a){ return a*b; } friend Point operator /(Point a,ld b){ return Point(a.x/b,a.y/b); } friend ld operator *(Point a,Point b){ return a.x*b.x+a.y*b.y; } ld len(){ return sqrt(x*x+y*y); } ld len2(){ return x*x+y*y; } Point unit(){ return *this/len(); } Point normal(){ return Point(-y,x); } }; struct Line{ Point l,r; Line(){} Line(Point _l,Point _r):l(_l),r(_r){} }; struct Circle{ Point o; ld r; Circle(){} Circle(Point _o,ld _r):o(_o),r(_r){} }; vector<Point> gci(Circle a,Line b){ Point h=a.o-(b.l-b.r).normal()*(a.o-b.l)/(b.l-b.r).len()*(b.l-b.r).normal().unit(); if(fabs(a.r*a.r-(a.o-h).len2())<eps) return {h}; double d=sqrt(a.r*a.r-(a.o-h).len2()); return {h+(b.l-b.r).unit()*d,h-(b.l-b.r).unit()*d}; } vector<Point> gci(Circle a,Circle b){ ld dis=(a.o-b.o).len(); if(dis>a.r+b.r+eps || dis+eps<fabs(a.r-b.r)) return {}; ld k=((a.o-b.o).len2()+a.r*a.r-b.r*b.r)/2.0/(a.o-b.o).len(); Point tmp=a.o+(b.o-a.o).unit()*k; Line t=Line(tmp,tmp+(b.o-a.o).normal()); return gci(a,t); } int n,fa[5]; Circle a[5]; int getfa(int x){ return x==fa[x]?x:fa[x]=getfa(fa[x]); } int main(){ freopen("1.in","r",stdin); freopen("1.out","w",stdout); scanf("%d",&n); int e=0,v=0,l=0; for(int i=1;i<=n;i++) scanf("%lf%lf%lf",&a[i].o.x,&a[i].o.y,&a[i].r),fa[i]=i; vector<Point> Inter,kkk=gci(a[3],a[2]); for(int i=1;i<=n;i++){ vector<Point> inter; for(int j=1;j<=n;j++) if(i!=j){ vector<Point> cur=gci(a[i],a[j]); if(cur.size()==0) continue; fa[getfa(i)]=getfa(j); for(Point u : cur) Inter.push_back(u),inter.push_back(u); } sort(inter.begin(),inter.end()); e+=unique(inter.begin(),inter.end())-inter.begin(); } sort(Inter.begin(),Inter.end()); //for(Point u : Inter) // printf("%.6lf %.6lf\n",u.x,u.y); v=unique(Inter.begin(),Inter.end())-Inter.begin(); for(int i=1;i<=n;i++) if(getfa(i)==i) l++; printf("%d\n",e-v+l+1); return 0; }