首页 > 代码库 > UVa 10969 (圆与圆之间的覆盖问题) Sweet Dream
UVa 10969 (圆与圆之间的覆盖问题) Sweet Dream
题意：
有n个按先后顺序放置的不同大小不同位置的圆，求所有可见圆弧的长度。
分析：
这道题应该是大白书上例题 LA 2572 (求可见圆盘的数量) Kanazawa 的加强版，整体框架都差不多。
对于每个圆求出与其他圆相交的交点所对应的幅角(转化到[0, 2π]中)，排个序，然后枚举每段弧的终点，如果不被后面放置的圆所覆盖则可见。
注意：
原本以为WA是精度问题，后来调大调小都一直WA，这里精度eps从1e-11到1e-13都没问题。
但是在判断弧的终点是否被圆所覆盖的时候要加上等号。也就是第64行代码中是<=而非<，一直被这个给坑惨了。
UVa的数据真的好强啊，Orz
1 #include <cstdio> 2 #include <cmath> 3 #include <vector> 4 #include <algorithm> 5 using namespace std; 6 7 const int maxn = 100 + 10; 8 const double eps = 1e-11; 9 const double PI = acos(-1.0); 10 const double TWO_PI = 2.0 * PI; 11 double radius[maxn]; 12 13 double NormalizeAngle(double ang) 14 { return ang - TWO_PI*floor(ang/TWO_PI); } 15 16 int dcmp(double x) 17 { 18 if(fabs(x) < eps) return 0; 19 return x < 0 ? -1 : 1; 20 } 21 22 struct Point 23 { 24 double x, y; 25 Point(double x=0, double y=0):x(x), y(y) {} 26 }p[maxn]; 27 typedef Point Vector; 28 29 bool operator == (const Point& A, const Point& B) 30 { return dcmp(A.x - B.x) == 0 && dcmp(A.y - B.y) == 0; } 31 32 Point operator - (const Point& A, const Point& B) 33 { return Point(A.x - B.x, A.y - B.y); } 34 35 double Dot(const Point& A, const Point& B) 36 { return A.x*B.x + A.y*B.y; } 37 38 double Length(const Vector& A) 39 { return sqrt(Dot(A, A)); } 40 41 double Angle(const Vector& A) 42 { return atan2(A.y, A.x); } 43 44 void GetCCIntersection(const Point& c1, double r1, const Point& c2, double r2, vector<double>& rad) 45 { 46 double d = Length(c1 - c2); 47 if(dcmp(d) == 0) return; 48 if(dcmp(d-r1-r2) > 0) return; 49 if(dcmp(d-fabs(r1-r2)) < 0) return; 50 51 double base = Angle(c2 - c1); 52 double ang = acos((r1*r1 + d*d - r2*r2) / (2.0*r1*d)); 53 rad.push_back(NormalizeAngle(base + ang)); 54 rad.push_back(NormalizeAngle(base - ang)); 55 } 56 57 int n; 58 59 bool isVisible(const Point& C, int id) 60 { 61 for(int i = id + 1; i < n; ++i) 62 { 63 double d = Length(C - p[i]); 64 if(dcmp(d - radius[i]) <= 0) return false; //这道题的关键所在 65 } 66 return true; 67 } 68 69 int main(void) 70 { 71 //freopen("10969in.txt", "r", stdin); 72 int T; 73 scanf("%d", &T); 74 while(T--) 75 { 76 scanf("%d", &n); 77 for(int i = 0; i < n; ++i) scanf("%lf%lf%lf", &radius[i], &p[i].x, &p[i].y); 78 79 double sum = 0.0; 80 for(int i = 0; i < n; ++i) 81 { 82 vector<double> rad; 83 rad.push_back(0.0); 84 rad.push_back(TWO_PI); 85 for(int j = 0; j < n; ++j) 86 { 87 if(j == i) continue; 88 GetCCIntersection(p[i], radius[i], p[j], radius[j], rad); 89 } 90 sort(rad.begin(), rad.end()); 91 92 for(int j = 0; j < rad.size() - 1; ++j) 93 { 94 double mid = (rad[j] + rad[j + 1]) / 2; 95 double ang = rad[j + 1] - rad[j]; 96 Point C(p[i].x + radius[i]*cos(mid), p[i].y + radius[i]*sin(mid)); 97 if(isVisible(C, i)) sum += radius[i] * ang; 98 } 99 }100 101 printf("%.3f\n", sum);102 }103 104 return 0;105 }
UVa 10969 (圆与圆之间的覆盖问题) Sweet Dream
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。