计算几何


2016-icpc-beijing

 ACM  计算几何 󰈭 2111字
H 二分答案然后跑圆的k次交即可。 因为学习完k次交后精疲力竭就不写完整这道题了。 贴一下用自己的码风写的板子。已更新入模版中。 给出n个圆的平面坐标和半径,能够获得所有圆k次交的面积。 cpp  󰄬 1const int manx = 1e2 + 10; 2const double eps = 1e-8; 3const double pi = acos(-1); 4 5inline int sgn(double x){return x < -eps? -1: x > eps? 1: 0;} 6inline double sqr(double x){return x * x;} 7 8struct CIRCLE{ 9 double x, y, r, angle; 10 int d; 11 CIRCLE(){d = 1; angle = 0;} 12 CIRCLE(double _x, double _y, double _angle = 0, int _d = 0){ 13 x = _x; y = _y; angle = _angle; d = _d; r = 0; 14 } 15 bool operator < (const CIRCLE &b)const{ 16 return sgn(r - b.r) == -1; 17 } 18}; 19 20inline double dis(CIRCLE a, CIRCLE b){return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y));} 21inline double cross(CIRCLE a, CIRCLE b, CIRCLE c){ 22 return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x); 23} 24 25//有两个交点返回true,以及两个交点的坐标和方位角,p1按照顺时针,p2按照逆时针 26bool cir_inter_cir(CIRCLE a, CIRCLE b, CIRCLE &p1, CIRCLE &p2){ 27 double d = dis(a, b); 28 if(sgn(d - a.r - b.r) >= 0 || sgn(abs(b.r - a.r) - d) >= 0) return false; 29 double cosa = (sqr(a.r) + sqr(d) - sqr(b.r)) / (2 * a.r * d); 30 double sina = sqrt(max(0., 1. - sqr(cosa))); 31 //旋转矩阵 [cosa, -sina; sina, cosa] 32 p1 = p2 = a; 33 p1.x += a.r / d * ((b.x - a.x) * cosa + (b.y - a.y) * -sina); 34 p1.y += a.r / d * ((b.x - a.x) * sina + (b.y - a.y) * cosa); 35 p2.x += a.r / d * ((b.x - a.x) * cosa + (b.y - a.y) * sina); 36 p2.y += a.r / d * ((b.x - a.x) * -sina + (b.y - a.y) * cosa); 37 return true; 38} 39 40bool cmp(const CIRCLE &a, const CIRCLE &b){ 41 if(sgn(a.angle - b.angle)) return sgn(a.angle - b.angle) == -1; 42 else return a.d > b.d; 43} 44 45double cal(CIRCLE a, CIRCLE p1, CIRCLE p2){ 46 double ans = sqr(a.r) * (p2.angle - p1.angle) - cross(a, p1, p2) + cross(CIRCLE(0, 0), p1, p2); 47 return ans / 2; 48} 49 50CIRCLE dot[maxn << 1]; 51double area[maxn]; 52void cirunion(CIRCLE cir[], int n){ 53 sort(cir, cir + n); 54 //记录每个圆被完全覆盖的次数,初始值显然为1 55 for(int i = 0; i < n; i++) for(int j = i + 1; j < n; j++) 56 if(sgn(dis(cir[i], cir[j]) + cir[i].r - cir[j].r) <= 0) cir[i].d++; 57 CIRCLE p1, p2; 58 for(int i = 0; i < n; i++){ 59 //针对每一个圆考虑它与所有其他圆的交 60 int cnt = 0, top = 0; 61 for(int j = 0; j < n; j++){ 62 if(i == j) continue; 63 if(!cir_inter_cir(cir[i], cir[j], p1, p2)) continue; 64 p1.angle = atan2(p1.y - cir[i].y, p1.x - cir[i].x); 65 p2.angle = atan2(p2.y - cir[i].y, p2.x - cir[i].x); 66 p1.d = -1; p2.d = 1; 67 dot[top++] = p1; dot[top++] = p2; 68 if(sgn(p2.angle - p1.angle) == 1) cnt++; 69 } 70 71 //加入起点终点位置 72 dot[top++] = CIRCLE(cir[i].x - cir[i].r, cir[i].y, -pi, -2); 73 dot[top++] = CIRCLE(cir[i].x - cir[i].r, cir[i].y, pi, 2); 74 sort(dot, dot + top, cmp); 75 int now = cir[i].d + cnt; 76 for(int j = 1; j < top; j++){ 77 area[now] += cal(cir[i], dot[j - 1], dot[j]); 78 now += dot[j].d; 79 } 80 } 81} 82 83CIRCLE cir[maxn]; 84int main(){ 85// Fastin; 86 int t; scanf("%d", &t); while(t--){ 87 clr(area, 0); 88 int n; scanf("%d", &n); 89 for(int i = 0; i < n; i++) scanf("%lf %lf %lf", &cir[i].x, &cir[i].y, &cir[i].r); 90 cirunion(cir, n); 91 for(int i = 1; i <= n; i++) printf("%.5f\n", area[i]); 92 } 93 return 0; 94} 因为网上基本没有讲解只有代码..oi-wiki甚至好像都没有收录这个算法,所以我学了好久才… ...