#include #include #include #include using namespace std ; const double pi = 3.14159265358979323846; struct seg { double a, b ; int q ; } ; struct pt { double x, y ; } ; struct arc { arc(struct circ &c, struct seg &seg) ; pt a, b ; pt ll, ur ; } ; struct circ { double r, x, y ; vector segs ; vector arcs ; } ; struct rect { double x1, y1, x2, y2, w, h ; } ; arc::arc(struct circ &c, struct seg &seg) { a = {c.x+c.r*cos(seg.a), c.y+c.r*sin(seg.a)} ; b = {c.x+c.r*cos(seg.b), c.y+c.r*sin(seg.b)} ; ll = {min(a.x, b.x), min(a.y, b.y)} ; ur = {max(a.x, b.x), max(a.y, b.y)} ; } vector circs ; void segfilter(circ &c, double a, double b) { int r = 0 ; int w = 0 ; double adda = -100 ; double addb = -100 ; int addq = -1 ; while (r < (int)c.segs.size()) { double aa = c.segs[r].a ; double bb = c.segs[r].b ; if (a <= aa && b >= bb) { r++ ; } else { if (r != w) c.segs[w] = c.segs[r] ; if (b <= aa || a >= bb) { // keep whole segment } else if (a <= aa) { // cut front if (r != w) c.segs[w] = c.segs[r] ; c.segs[w].a = b ; } else { // cut back, or split c.segs[w].b = a ; if (b < bb) { if (r != w) { w++ ; c.segs[w] = {b, bb, c.segs[r].q} ; } else { adda = b ; addb = bb ; addq = c.segs[r].q ; } } } r++ ; w++ ; } } c.segs.resize(w) ; if (adda != -100) c.segs.push_back({adda, addb, addq}) ; } void addpts(circ &c, double x1, double y1, double x2, double y2) { double a = atan2(y1-c.y, x1-c.x) ; double b = atan2(y2-c.y, x2-c.x) ; if (a > b) { segfilter(c, a, pi) ; segfilter(c, -pi, b) ; } else { segfilter(c, a, b) ; } } double bound(double v, double lo, double hi) { return min(hi, max(lo, v)) ; } double getang(double dx, double dy, const seg &seg) { switch(seg.q) { case 1: dx = - dx ; dy = - dy ; break ; case 2: dy = - dy ; break ; case 3: break ; case 4: dx = - dx ; break ; } return atan2(dy, dx) ; } int main() { cout << setprecision(15) ; int n, q ; cin >> n >> q ; circs.resize(n) ; for (auto &c: circs) { cin >> c.x >> c.y >> c.r ; c.segs.push_back({-pi,-pi*0.5, 1}) ; c.segs.push_back({-pi*0.5,0, 2}) ; c.segs.push_back({0,pi*0.5, 3}) ; c.segs.push_back({pi*0.5,pi, 4}) ; } for (int i=0; i c2.r) { c2.segs.clear() ; } else { c1.segs.clear() ; } } else if (d2 < c1.r + c2.r) { double xx = (d2 * d2 - c2.r * c2.r + c1.r * c1.r) / (2 * d2) ; double yy = sqrt(c1.r * c1.r - xx * xx) ; double xc = xx * (c2.x - c1.x) ; double yc = xx * (c2.y - c1.y) ; double xs = yy * (c2.y - c1.y) ; double ys = -yy * (c2.x - c1.x) ; double x1 = (xc + xs) / d2 + c1.x ; double y1 = (yc + ys) / d2 + c1.y ; double x2 = (xc - xs) / d2 + c1.x ; double y2 = (yc - ys) / d2 + c1.y ; addpts(c1, x1, y1, x2, y2) ; addpts(c2, x2, y2, x1, y1) ; } } } for (auto &c: circs) for (auto &seg: c.segs) c.arcs.push_back(arc(c, seg)) ; for (int i=0; i> r.x1 >> r.y1 >> r.w >> r.h ; r.x2 = r.x1 + r.w ; r.y2 = r.y1 + r.h ; double s = 0 ; for (auto &c: circs) { for (int k=0; k<(int)c.segs.size(); k++) { auto &arc = c.arcs[k] ; auto &seg = c.segs[k] ; if (arc.ll.x >= r.x2 || arc.ur.x <= r.x1) // to left or right continue ; if (arc.ur.y <= r.y1) // below continue ; if (arc.ll.y >= r.y2) { // above s += r.h * (bound(arc.b.x, r.x1, r.x2) - bound(arc.a.x, r.x1, r.x2)) ; continue ; } auto arc2 = arc ; // writable versions auto seg2 = seg ; if ((arc.ll.x < r.x1 || arc.ur.x > r.x2 || arc.ll.y < r.y1 || arc.ur.y > r.y2)) { if (arc2.ll.x < r.x1) { // trim left side double dx = abs(c.x - r.x1) ; double na = getang(dx, sqrt(c.r*c.r-dx*dx), seg2) ; if (seg2.q > 2) seg2.b = na ; else seg2.a = na ; struct arc arc3(c, seg2) ; arc2 = arc3 ; } if (arc2.ur.x > r.x2) { // trim right side double dx = abs(c.x - r.x2) ; double na = getang(dx, sqrt(c.r*c.r-dx*dx), seg2) ; if (seg2.q <= 2) seg2.b = na ; else seg2.a = na ; struct arc arc3(c, seg2) ; arc2 = arc3 ; } if (arc2.ll.y < r.y1) { // trim bot double dy = abs(c.y - r.y1) ; double na = getang(sqrt(c.r*c.r-dy*dy), dy, seg2) ; if (seg2.q > 1 && seg2.q < 4) seg2.a = na ; else seg2.b = na ; struct arc arc3(c, seg2) ; arc2 = arc3 ; } if (arc2.ur.y > r.y2) { // trim top double dy = abs(c.y - r.y2) ; double na = getang(sqrt(c.r*c.r-dy*dy), dy, seg2) ; if (seg2.q <= 1 || seg2.q >= 4) seg2.a = na ; else seg2.b = na ; if (seg2.b > seg2.a) { struct arc arc3(c, seg2) ; s -= r.h * (arc3.b.x - arc3.a.x - arc2.b.x + arc2.a.x) ; arc2 = arc3 ; } else { s += r.h * (bound(arc2.b.x, r.x1, r.x2) - bound(arc2.a.x, r.x1, r.x2)) ; } } } double theta = seg2.b - seg2.a ; if (theta > 0) { s += 0.5 * (arc2.a.y + arc2.b.y - 2 * r.y1) * (arc2.b.x - arc2.a.x) ; if ((seg2.q > 2) == (arc2.b.x > arc2.a.x)) { // above; add s += 0.5 * c.r * c.r * (theta - sin(theta)) ; } else { // below; subtract s -= 0.5 * c.r * c.r * (theta - sin(theta)) ; } } } } cout << -100*s/(r.w*r.h) << endl ; } }