UVA10969计算几何+交叉圆形成的圆弧长

  1 /*
  2 UVA10969计算几何
  3 这道题和UVALive 2572类似
  4 1、枚举每个圆上的可见圆弧，弧长之和即为答案
  5 2、圆上的点按照相邻依次排序的关键量为极角（0,2PI）
  6 3、用中心点代替圆弧本身是否被圆覆盖
  7 
  8 */
  9 #include <stdio.h>
 10 #include <stdlib.h>
 11 #include <string.h>
 12 #include <math.h>
 13 #include <ctype.h>
 14 #include <string>
 15 #include <iostream>
 16 #include <sstream>
 17 #include <vector>
 18 #include <queue>
 19 #include <stack>
 20 #include <map>
 21 #include <list>
 22 #include <set>
 23 #include <algorithm>
 24 #define rec(i,n) for(int i=1;i<=n;i++)
 25 #define INF 0x3f3f3f3f
 26 #define eps 1e-7
 27 #define eps2 1e-3
 28 using namespace std;
 29 
 30 double move[5][2]= {{0,eps2},{0,-eps2},{eps2,0},{-eps2,0}};
 31 //微小偏移量，至少是3个不同的方向，这里取上下左右四个比较方便,记住偏移量的数量就比eps本身要大，不然等于无效
 32 struct Point
 33 {
 34     double x,y;
 35     Point() {}
 36     Point(double xx,double yy)
 37     {
 38         x=xx;
 39         y=yy;
 40     }
 41 };
 42 struct Circle
 43 {
 44     Point O;
 45     double r;
 46     Circle() {}
 47     Circle(Point O1,double r1)
 48     {
 49         O=O1;
 50         r=r1;
 51     }
 52     Point point(double a)
 53     {
 54         return Point(O.x+cos(a)*r,O.y+sin(a)*r);
 55     }
 56 };
 57 typedef Point Vector;
 58 
 59 bool operator==(Point A,Point B)
 60 {
 61     if ((fabs(A.x-B.x)<1e-10) && (fabs(A.y-B.y)<1e-10)) return true;
 62     else return false;
 63 }
 64 Vector operator-(Point A,Point B)//表示A指向B
 65 {
 66     return Vector(A.x-B.x,A.y-B.y);
 67 }
 68 Vector operator*(Vector A,double k)
 69 {
 70     return Vector(A.x*k,A.y*k);
 71 }
 72 Vector operator+(Point A,Point B)//表示A指向B
 73 {
 74     return Vector(B.x+A.x,B.y+A.y);
 75 }
 76 double Dot(Vector A,Vector B)
 77 {
 78     return A.x*B.x+A.y*B.y;
 79 }
 80 double Length(Vector A)
 81 {
 82     return sqrt(Dot(A,A));
 83 }
 84 double Cross(Vector A,Vector B)
 85 {
 86     return A.x*B.y-A.y*B.x;
 87 }
 88 int dcmp(double x)
 89 {
 90     if(fabs(x)<1e-10) return 0;
 91     else if(x>0) return 1;
 92     else return -1;
 93 }
 94 double angle(Vector v)
 95 {
 96     return atan2(v.y,v.x);
 97 }
 98 int getCircleInter(Circle c1, Circle c2,vector<Point>& sol1,vector<Point>& sol2)
 99 {
100     double d=Length(c1.O-c2.O);
101     if(dcmp(d)==0)
102     {
103         if(dcmp(c1.r-c2.r)==0) return -1;//两圆重合
104         return 0;
105     }
106     if(dcmp(c1.r+c2.r-d)<0) return 0;
107     if(dcmp(fabs(c1.r-c2.r)-d)>0) return 0;
108 
109     double a=angle(c2.O-c1.O);
110     double da=acos((c1.r*c1.r+d*d-c2.r*c2.r)/(2*c1.r*d));
111 
112     Point p1=c1.point(a-da),p2=c1.point(a+da);
113 
114     if (p1==p2) return 1;
115     sol1.push_back(p1),sol2.push_back(p1);
116     sol1.push_back(p2);
117     sol2.push_back(p2);
118     return 2;
119 }
120 int n;
121 Circle CC[110];//圆
122 vector<Point> CP[110];//每个圆上的交点
123 double Arf[410];//圆心角
124 double getangle(Vector v)//核心函数，返回向量的极角
125 {
126     double x=v.x;
127     double y=v.y;
128     if(fabs(y)<eps) if(x>0) return 0;
129         else return M_PI;
130     if(fabs(x)<eps) if(y>0) return 0.5*M_PI;
131         else return 1.5*M_PI;
132     double arf=acos(fabs(x)/(sqrt(x*x+y*y)));
133     if(x>0) if(y>0) return arf;
134         else return 2*M_PI-arf;
135     if(y>0) return M_PI-arf;
136     else return M_PI+arf;
137 }
138 Point GetMid(double a,double b,double r,double x,double y)//圆上两点，获得中点的坐标
139 {
140     double arf=(b+a)/2;
141     double xx=r*cos(arf)+x;
142     double xy=r*sin(arf)+y;
143     Point P=Point(xx,xy);
144 //    P.print();
145     return P;
146 }
147 bool PInCircle(Point P,Circle C)//判断点在圆内
148 {
149     double dis=Length(P-C.O);
150     if (dis-C.r>1e-10) return false;
151     else return true;
152 }
153 int cas;
154 int main()
155 {
156     cin>>cas;
157     while(cas--)
158     {
159         double ans=0.0;
160         cin>>n;
161         for(int i=1; i<=n; i++)//读取信息
162         {
163             double x,y,r;
164             cin>>r>>x>>y;
165             x=1e10*x;y=1e10*y;r=1e10*r;//这里非常重要，因为我们是进行点的微小移动，这样等于将整张图放大了，保留了精度
166             CC[i]=Circle(Point(x,y),r);
167         }
168         for(int i=1; i<=n; i++) CP[i].clear();
169         for(int i=1; i<n; i++)//获得圆上的交点
170             for(int j=i+1; j<=n; j++)
171                 getCircleInter(CC[i],CC[j],CP[i],CP[j]);
172         for(int i=1; i<=n; i++) //枚举前n个圆上的圆弧
173         {//当CP[i].size()为0时要特判，这是和其他圆的关系要么包含，要么被包含，比较半径即可
174             int k=CP[i].size();
175             Arf[0]=0.0;
176             Arf[1]=2*M_PI;//添加两个点，局部细分：这里也是重点：图形离散化解决了穷举的难题，同时也意味着可加上一些特殊的点
177             //上面两个点的加入，也解决了圆上0和1个点的问题
178             for(int j=0; j<k; j++)
179             {
180                 double arf=getangle(CP[i][j]-CC[i].O);//重点：角度的计算，其实就是圆心指向圆上的点的向量的角度啊
181                 Arf[j+2]=arf;
182             }
183             sort(Arf,Arf+k+2);
184             k=unique(Arf,Arf+k+2)-Arf;//去除重复点
185 
186             for(int j=0; j<k-1; j++) //枚举每条弧
187             {
188                 Point Mid=GetMid(Arf[j],Arf[j+1],CC[i].r,CC[i].O.x,CC[i].O.y);
189 
190                 bool ok=true;//表示这条圆弧可见
191                 for(int l=i+1; l<=n; l++) //判断中点是否可见
192                     if (PInCircle(Mid,CC[l])) ok=false;
193                 if(ok) ans+=(Arf[j+1]-Arf[j])*CC[i].r;
194             }
195         }
196 
197         printf("%.3lf\n",(ans/1e10));//放缩回来
198     }
199     return 0;
200 }