Why so serious? --[NKU]schindlerlee

zju2589 不重合的n个圆形成的区域


  1 /* 
  2  * SOUR:zju2589
  3  * ALGO:computational geomtry 计算平面上不重合的n个圆形成的区域
  4  * 基本的方法,如图所示,将所有圆之间的交点作为点,将在同一个圆上的所有交点之间的弧作
  5  * 为边建立一张有向图,之后可以利用平面图的欧拉定理
  6  *           V - E + F = 2
  7  * 由于V已知,E已知,F就可以求出来了。
  8  * 由于欧拉定理是对一张无向连通图成立的,如果图有多个连通块的时候需要对欧拉定理做一些
  9  * 修改。由于多个有向图的面共享最外边的面,所以设联通块的个数为n
 10  * V - E + F = 2 * n , 但是需要减去n个联通块共享的最大平面
 11  * 所以 F = n + 1 + E - V;
 12  * DATE: 2010年 07月 08日 星期四 14:49:41 CST
 13  * COMM:5
 14  * */
 15 const int N = 64;
 16 const double eps = 1e-8;
 17 int n, vis[N], g[N][N];
 18 double r[N];
 19 struct point_t {
 20     double x, y;
 21     point_t(){}
 22     point_t(double a, double b){x = a, y = b;} 
 23 }c[N];
 24 
 25 int dcmp(double x) { return (x > eps) - (x < -eps);} 
 26 bool operator < (point_t a,point_t b) 
 27 {
 28   if (dcmp(a.x - b.x)) {
 29       return a.x < b.x;
 30   }
 31   return dcmp(a.y - b.y) < 0;
 32 }
 33 
 34 point_t operator + (point_t a, point_t b) { return point_t(a.x+b.x, a.y+b.y);}
 35 point_t operator - (point_t a, point_t b) { return point_t(a.x-b.x, a.y-b.y);}
 36 double dist(point_t a, point_t b) { return hypot(a.x-b.x, a.y-b.y);}
 37 double sqr(double x) { return x * x;}
 38 point_t normal(point_t a) { return point_t(a.x / hypot(a.x, a.y), a.y / hypot(a.x, a.y));}
 39 point_t scale(point_t a, double fac) { return point_t(a.x * fac, a.y * fac);}
 40 bool intersect(point_t c1, double r1, point_t c2, double r2, point_t &a, point_t &b)
 41 {
 42   double d = dist(c1, c2);
 43   if (d < fabs(r1 - r2) - eps || d > r1 + r2 + eps) {
 44       return false;
 45   }
 46   double len = (sqr(r1) - sqr(r2) + sqr(d)) / 2.0 / d;
 47   double h = sqrt(sqr(r1) - sqr(len));
 48   point_t t = normal(c2 - c1);
 49   point_t p = c1 + scale(t, len);
 50   point_t v = scale(point_t(-t.y, t.x), h);
 51   a = p + v, b = p -v;
 52   return true;
 53 }
 54 
 55 void init()
 56 {
 57   int i;
 58   memset(g, 0sizeof(g));
 59   memset(vis, 0sizeof(vis));
 60   for (i = 0;i < n;i++) {
 61       g[i][i] = 1;
 62   }
 63 }
 64 
 65 int main()
 66 {
 67   int testcase, i, j, k;
 68   scanf("%d"&testcase);
 69   while (testcase--) {
 70       scanf("%d"&n);
 71       set <point_t> allpoint, p[64];
 72       for (i = 0;i < n;i++) {
 73           scanf("%lf %lf %lf"&c[i].x, &c[i].y, &r[i]);
 74       }
 75       init();
 76       for (i = 0;i < n;i++) {
 77           for (j = i + 1;j < n;j++) {
 78               point_t a, b;
 79               if (intersect(c[i], r[i], c[j], r[j], a, b)) {
 80                   allpoint.insert(a), allpoint.insert(b);
 81                   p[i].insert(a), p[i].insert(b);
 82                   p[j].insert(a), p[j].insert(b);
 83                   g[i][j] = g[j][i] = 1;
 84               }
 85           }
 86       }
 87       for (k = 0;k < n;k++) {
 88           for (i = 0;i < n;i++) {
 89               for (j = 0;j < n;j++) {
 90                   g[i][j] |= g[i][k] & g[k][j];
 91               }
 92           }
 93       }
 94       int f = 1;
 95       for (i = 0;i < n;i++) {
 96           f += p[i].size();
 97           if (!vis[i]) {
 98               f += 1;
 99               for (j = 0;j < n;j++) {
100                   vis[j] |= g[i][j];
101               }
102           }
103       }
104       f -= allpoint.size();
105       printf("%d\n", f);
106   } 
107   return 0;
108 }
109 
110 

posted on 2010-07-08 22:06 schindlerlee 阅读(1627) 评论(0)  编辑 收藏 引用 所属分类: 解题报告


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理