首页 > 代码库 > zoj2589Circles(平面图的欧拉定理)
zoj2589Circles(平面图的欧拉定理)
链接
连通图中:
设一个平面图形的顶点数为n,划分区域数为r,一笔画笔数为也就是边数m,则有:
n+r-m=2
那么不算外面的那个大区域的话 就可以写为 n+r-m = 1
那么这个题就可以依次求出每个连通图的r = m-n+1 累加起来 最后加上最外面那个平面。
注意交点的去重,对于一个圆的边数其实就是交点的数量(排除没有交点的情况)
1 #include <iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<stdlib.h> 6 #include<vector> 7 #include<cmath> 8 #include<queue> 9 #include<set> 10 using namespace std; 11 #define N 55 12 #define LL long long 13 #define INF 0xfffffff 14 const double eps = 1e-10; 15 const double pi = acos(-1.0); 16 const double inf = ~0u>>2; 17 18 struct point 19 { 20 double x,y; 21 point(double x=0,double y=0):x(x),y(y){} 22 }; 23 vector<point>ed[N]; 24 vector<int>dd[N]; 25 vector<point>td[N]; 26 struct circle 27 { 28 point c; 29 double r; 30 point ppoint(double a) 31 { 32 return point(c.x+cos(a)*r,c.y+sin(a)*r); 33 } 34 }; 35 circle cp[N],cq[N]; 36 int fa[N]; 37 typedef point pointt; 38 pointt operator -(point a,point b) 39 { 40 return point(a.x-b.x,a.y-b.y); 41 } 42 43 int dcmp(double x) 44 { 45 if(fabs(x)<eps) return 0; 46 return x<0?-1:1; 47 } 48 49 bool operator == (const point &a,const point &b) 50 { 51 return dcmp(a.x-b.x)==0&&dcmp(a.y-b.y)==0; 52 } 53 double dis(point a) 54 { 55 return sqrt(a.x*a.x+a.y*a.y); 56 } 57 double angle(point a)//计算向量极角 58 { 59 return atan2(a.y,a.x); 60 } 61 double sqr(double x) { 62 63 return x * x; 64 65 } 66 67 bool intersection(const point& o1, double r1, const point& o2, double r2,int k,int kk) 68 { 69 double d = dis(o1- o2); 70 if (d < fabs(r1 - r2) - eps || d > r1 + r2 + eps) 71 { 72 return false; 73 } 74 double cosa = (sqr(r1) + sqr(d) - sqr(r2)) / (2 * r1 * d); 75 double sina = sqrt(max(0., 1. - sqr(cosa))); 76 point p1 = o1,p2 = o1; 77 p1.x += r1 / d * ((o2.x - o1.x) * cosa + (o2.y - o1.y) * -sina); 78 p1.y += r1 / d * ((o2.x - o1.x) * sina + (o2.y - o1.y) * cosa); 79 p2.x += r1 / d * ((o2.x - o1.x) * cosa + (o2.y - o1.y) * sina); 80 p2.y += r1 / d * ((o2.x - o1.x) * -sina + (o2.y - o1.y) * cosa); 81 //cout<<p1.x<<" --"<<p2.x<<" "<<o1.x<<" "<<o1.y<<" "<<o2.x<<" "<<o2.y<<endl; 82 //printf("%.10f %.10f %.10f %.10f\n",p1.x,p1.y,p2.x,p2.y); 83 ed[k].push_back(p1); 84 ed[k].push_back(p2); 85 ed[kk].push_back(p1); 86 ed[kk].push_back(p2); 87 88 return true; 89 } 90 bool cmp(circle a, circle b) 91 { 92 if(dcmp(a.r-b.r)==0) 93 { 94 if(dcmp(a.c.x-b.c.x)==0) 95 return a.c.y<b.c.y; 96 return a.c.x<b.c.x; 97 } 98 return a.r<b.r; 99 }100 bool cmpp(point a,point b)101 {102 if(dcmp(a.x-b.x)==0)103 return a.y<b.y;104 return a.x<b.x;105 }106 int find(int x)107 {108 if(fa[x]!=x)109 {110 fa[x] = find(fa[x]);111 return fa[x];112 }113 return x;114 }115 int main()116 {117 int t,i,j,n;118 cin>>t;119 while(t--)120 {121 scanf("%d",&n);122 for(i = 1; i <= n ;i++)123 {124 ed[i].clear();fa[i] = i;125 dd[i].clear();126 td[i].clear();127 }128 for(i = 1; i <= n ;i++)129 scanf("%lf%lf%lf",&cp[i].c.x,&cp[i].c.y,&cp[i].r);130 sort(cp+1,cp+n+1,cmp);131 int g = 1;132 cq[g] = cp[g];133 for(i = 2; i <= n; i++)134 {135 if(cp[i].c==cp[i-1].c&&dcmp(cp[i].r-cp[i-1].r)==0)136 continue;137 cq[++g] = cp[i];138 }139 for(i = 1; i <= g; i++)140 {141 for(j = i+1 ; j <= g; j++)142 {143 int flag = intersection(cq[i].c,cq[i].r,cq[j].c,cq[j].r,i,j);144 if(flag == 0) continue;145 int tx = find(i),ty = find(j);146 fa[tx] = ty;147 }148 }149 for(i = 1; i <= g; i++)150 {151 int fx = find(i);152 dd[fx].push_back(i);153 }154 int B=0,V=0;155 int ans = 0;156 int num = 0;157 for(i = 1 ; i <= g; i++)158 {159 if(dd[i].size()==0) continue;160 B = 0,V = 0;161 for(j = 0 ;j < dd[i].size() ; j++)162 {163 int u = dd[i][j];164 if(ed[u].size()==0)165 {166 B++;167 continue;168 }169 sort(ed[u].begin(),ed[u].end(),cmpp);170 td[i].push_back(ed[u][0]);171 int o = 1;172 for(int e = 1 ; e < ed[u].size() ; e++)173 {174 //printf("%.10f %.10f\n",ed[u][e].x,ed[u][e].y);175 td[i].push_back(ed[u][e]);176 if(ed[u][e]==ed[u][e-1]) continue;177 else o++;178 }179 B+=o;180 }181 sort(td[i].begin(),td[i].end(),cmpp);182 V+=1;183 // cout<<td[i].size()<<endl;184 for(j = 1; j < td[i].size() ; j++)185 {186 //printf("%.10f %.10f\n",td[i][j].x,td[i][j].y);187 if(td[i][j]==td[i][j-1]) continue;188 else V++;189 190 }191 // cout<<B+1-V<<" "<<B<<" "<<V<<endl;192 ans+=B+1-V;193 }194 cout<<1+ans<<endl;195 }196 return 0;197 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。