首页 > 代码库 > LA 2572 Kanazawa
LA 2572 Kanazawa
题意：
把n个圆盘依次放到桌面上，按照放置的先后顺序给出这n个圆盘的圆心和半径，输出有多少个圆盘可见(即未被全部覆盖)。
分析：
题中说对输入数据进行微小扰动后答案不变。
所露出的部分都是由若干小圆弧组成的。因此求出每个圆与其他圆相交的小圆弧，取圆弧的终点，分别向里和向外移动一个很小的距离的到P‘。标记包含P‘的最上面的那个圆为可见。
1 //#define LOCAL 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <cmath> 6 #include <vector> 7 using namespace std; 8 9 const int maxn = 110; 10 const double PI = acos(-1.0); 11 const double Two_PI = PI * 2; 12 const double eps = 5 * 1e-13; 13 int n; 14 double radius[maxn]; 15 bool vis[maxn]; 16 17 int dcmp(double x) 18 { 19 if(fabs(x) < eps) return 0; 20 else return x < 0 ? -1 : 1; 21 } 22 23 struct Point 24 { 25 double x, y; 26 Point(double x=0, double y=0):x(x), y(y) {} 27 }; 28 typedef Point Vector; 29 Point operator + (Point A, Point B) { return Point(A.x+B.x, A.y+B.y); } 30 Point operator - (Point A, Point B) { return Point(A.x-B.x, A.y-B.y); } 31 Vector operator * (Vector A, double p){ return Vector(A.x*p, A.y*p); } 32 Vector operator / (Vector A, double p){ return Vector(A.x/p, A.y/p); } 33 Point center[maxn]; 34 35 double Dot(Vector A, Vector B){ return A.x*B.x + A.y*B.y; } 36 double Length(Vector A){ return sqrt(Dot(A, A)); } 37 double angle(Vector v) { return atan2(v.y, v.x); } 38 double NormalizeAngle(double rad) 39 {//将所求角度化到0到2π之间 40 return rad - Two_PI*(floor(rad/Two_PI)); 41 } 42 43 void getCCIntersection(Point c1, double r1, Point c2, double r2, vector<double>& rad) 44 { 45 double d = Length(c1 - c2); 46 if(dcmp(d) == 0) return; 47 if(dcmp(d-r1-r2) > 0) return; 48 if(dcmp(d-fabs(r1-r2)) < 0) return; 49 50 double a = angle(c2-c1); 51 double ag = acos((r1*r1+d*d-r2*r2)/(2*r1*d)); 52 rad.push_back(NormalizeAngle(a + ag)); 53 rad.push_back(NormalizeAngle(a - ag)); 54 } 55 56 int topmost(Point P) 57 { 58 for(int i = n-1; i >= 0; --i) 59 if(Length(P-center[i]) < radius[i]) return i; 60 return -1; 61 } 62 63 int main(void) 64 { 65 #ifdef LOCAL 66 freopen("2572in.txt", "r", stdin); 67 #endif 68 69 while(scanf("%d", &n) == 1 && n) 70 { 71 for(int i = 0; i < n; ++i) 72 scanf("%lf%lf%lf", ¢er[i].x, ¢er[i].y, &radius[i]); 73 memset(vis, 0, sizeof(vis)); 74 75 for(int i = 0; i < n; ++i) 76 { 77 vector<double> rad; 78 rad.push_back(0.0); 79 rad.push_back(Two_PI); 80 for(int j = 0; j < n && j != i; ++j) 81 getCCIntersection(center[i], radius[i], center[j], radius[j], rad); 82 sort(rad.begin(), rad.end()); 83 84 for(int j = 0; j < rad.size(); ++j) 85 { 86 double mid = (rad[j] + rad[j+1]) / 2.0; 87 for(int side = -1; side <= 1; side += 2) 88 { 89 double r = radius[i] + side*eps; 90 int t = topmost(Point(center[i].x+r*cos(mid), center[i].y+r*sin(mid))); 91 if(t >= 0) vis[t] = true; 92 } 93 } 94 } 95 int ans = 0; 96 for(int i = 0; i < n; ++i) if(vis[i]) ++ans; 97 printf("%d\n", ans); 98 } 99 100 return 0;101 }
LA 2572 Kanazawa
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。