#include #include #include #include #include #include #include using namespace std; template struct Point { typedef Point P; T x, y; explicit Point(T x=0, T y=0) : x(x), y(y) {} bool operator<(P p) const { return tie(x,y) < tie(p.x,p.y); } bool operator==(P p) const { return tie(x,y)==tie(p.x,p.y); } P operator+(P p) const { return P(x+p.x, y+p.y); } P operator-(P p) const { return P(x-p.x, y-p.y); } P operator*(T d) const { return P(x*d, y*d); } P operator/(T d) const { return P(x/d, y/d); } T dot(P p) const { return x*p.x + y*p.y; } T cross(P p) const { return x*p.y - y*p.x; } T cross(P a, P b) const { return (a-*this).cross(b-*this); } T dist2() const { return x*x + y*y; } double dist() const { return sqrt((double)dist2()); } // angle to x-axis in interval [-pi, pi] double angle() const { return atan2(y, x); } P unit() const { return *this/dist(); } // makes dist()=1 P perp() const { return P(-y, x); } // rotates +90 degrees P normal() const { return perp().unit(); } // returns point rotated 'a' radians ccw around the origin P rotate(double a) const { return P(x*cos(a)-y*sin(a),x*sin(a)+y*cos(a)); } }; typedef long long ll; typedef pair, int> circle; bool sortbysize(circle a, circle b) { return a.second < b.second; } void prune(vector& circles) { for(int i = 0; i < circles.size();) { bool bad = false; for(int j = i+1; !bad && j < circles.size(); j++) { ll d2 = (circles[i].first - circles[j].first).dist2(); ll extra = circles[j].second - circles[i].second; if(extra * extra >= d2) bad = true; } if(bad) circles.erase(circles.begin() + i); else i++; } } typedef Point P; bool circleIntersection(P a, P b, double r1, double r2, pair* out) { P delta = b - a; assert(delta.x || delta.y || r1 != r2); if (!delta.x && !delta.y) return false; double r = r1 + r2, d2 = delta.dist2(); double p = (d2 + r1*r1 - r2*r2) / (2.0 * d2); double h2 = r1*r1 - p*p*d2; if (d2 > r*r || h2 < 0) return false; P mid = a + delta*p, per = delta.perp() * sqrt(h2 / d2); *out = {mid + per, mid - per}; return true; } double triarea(P a, P b, P c) { double ret = 0; ret += a.cross(b); ret += b.cross(c); ret += c.cross(a); return fabs(ret) / 2; } const double PI = acos(-1); typedef pair> arc; double computesmallarcarea(ll radius, double xlhs, double xrhs) { // imagine the circle drawn with radius, and draw vertical lines at xlhs and xrhs // and then draw a horizontal line at the same place as xrhs // return the area of that section double ylhs = sqrt(radius*radius - xlhs*xlhs); double yrhs = sqrt(radius*radius - xrhs*xrhs); double thetalhs = atan2(ylhs, xlhs); double thetarhs = atan2(yrhs, xrhs); double smallarc = radius * radius / 2.; smallarc *= (thetalhs - thetarhs); P a = P(xlhs, xlhs * yrhs / xrhs); P d = P(xlhs, yrhs); double tris = 0; tris += triarea(P(0, 0), a, P(xlhs, ylhs)); tris += triarea(d, a, P(xrhs, yrhs)); return smallarc - tris; } double fourthquadintersection(ll radius, pair angles, ll xa, ll ya, ll xb, ll yb) { if(ya >= 0 || xb <= 0 || xa >= radius) return 0; assert(xa < xb); assert(ya < yb); assert(angles.first <= angles.second); assert(angles.first >= -PI/2); assert(angles.second <= 0); xa = max(xa, 0LL); double rectanglearea = 0; double xlhs = radius * cos(angles.first); if(xlhs >= xb) return 0; double xrhs = radius * cos(angles.second); if(xrhs <= xa) return 0; xlhs = max(xlhs, (double)xa); xrhs = min(xrhs, (double)xb); assert(xlhs <= xrhs); // start by computing the area under the circle that is upper-bounded by the rectangle and not the arc // in order for any part of the rectangle to be pertinent, at xrhs we have to be above yb double yrhs = -sqrt(radius * radius - xrhs * xrhs); if(yrhs > yb) { if(-yb >= radius) { // the rectangle is entirely below the circle return (xrhs - xlhs) * (yb - ya); } double xthresh = sqrt(radius * radius - yb * yb); if(xthresh <= xlhs) { // the rectangle is entirely below the circle? return (xrhs - xlhs) * (yb - ya); } // uh oh assert(xthresh >= xlhs); rectanglearea = (xrhs - xthresh) * (yb - ya); } // now we need to compute the area under the arc // start by shrinking the interval to be tight if(yb < 0) { double xthresh = sqrt(radius * radius - yb * yb); xrhs = min(xrhs, xthresh); } double xthresh = sqrt(radius * radius - ya * ya); xlhs = max(xlhs, xthresh); if(xlhs >= xrhs) return rectanglearea; // this interval is now tight double smallarc = computesmallarcarea(radius, xlhs, xrhs); double totarea = -smallarc; // xrhs might still leave some area above... yrhs = -sqrt(radius * radius - xrhs * xrhs); if(yrhs <= yb) totarea -= (yb - yrhs) * (xrhs - xlhs); return (rectanglearea + totarea) + (xrhs - xlhs) * (yb - ya); } double firstquadintersection(ll radius, pair angles, ll xa, ll ya, ll xb, ll yb) { if(xa >= radius || ya >= radius || xb <= 0) return 0; assert(xa < xb); assert(ya < yb); assert(angles.first <= angles.second); assert(angles.first >= 0); assert(angles.second <= PI/2); xa = max(xa, 0LL); // start by computing the area that is upper-bounded by the rectangle and not the arc double xlhs = radius * cos(angles.second); if(xlhs >= xb) return 0; double xrhs = radius * cos(angles.first); if(xrhs <= xa) return 0; xlhs = max(xlhs, (double)xa); xrhs = min(xrhs, (double)xb); assert(xlhs <= xrhs); // in order for any part of the rectangle to be pertinent, at xlhs we have to be above the rectangle double ylhs = sqrt(radius * radius - xlhs * xlhs); double rectanglearea = 0; if(ylhs > yb) { if(yb <= 0) { // the rectangle is entirely below the circle? return (xrhs - xlhs) * (yb - ya); } double xthresh = sqrt(radius * radius - yb * yb); if(xthresh >= xrhs) { // the rectangle is still entirely below the circle? return (xrhs - xlhs) * (yb - ya); } // uh oh assert(xthresh >= xlhs); rectanglearea = (xthresh - xlhs) * (yb - ya); } // now we need to compute the area under the arc // start by shrinking the interval to be tight assert(yb > 0); double xthresh = sqrt(radius * radius - yb * yb); xlhs = max(xlhs, xthresh); if(ya > 0) { // shrink the right side xthresh = sqrt(radius * radius - ya * ya); xrhs = min(xrhs, xthresh); } if(xlhs >= xrhs) return rectanglearea; assert(xlhs < xrhs); double arcarea = computesmallarcarea(radius, xlhs, xrhs); double yrhs = sqrt(radius*radius - xrhs*xrhs); // don't forget area under that is rectangular! if(yrhs >= ya) rectanglearea += (yrhs - ya) * (xrhs - xlhs); return rectanglearea + arcarea; } void qry(const vector& arcn, const vector& arct) { ll xa, ya, xb, yb; bool uset = false; { cin >> xa >> ya; int w, h; cin >> w >> h; xb = xa + w; yb = ya + h; if(w < h) { swap(xa, ya); swap(xb, yb); uset = true; } } double tot = 0; for(auto out: uset ? arct : arcn) { double delta = 0; if(out.second.second <= PI/2) { delta = firstquadintersection( out.first.second, out.second, xa-out.first.first.x, ya-out.first.first.y, xb-out.first.first.x, yb-out.first.first.y ); } else if(out.second.second <= PI) { delta = firstquadintersection( out.first.second, make_pair(PI - out.second.second, PI - out.second.first), out.first.first.x-xb, ya-out.first.first.y, out.first.first.x-xa, yb-out.first.first.y ); } else if(out.second.second <= 3*PI/2) { delta = -fourthquadintersection( out.first.second, make_pair(-out.second.second + PI, -out.second.first + PI), out.first.first.x-xb, ya-out.first.first.y, out.first.first.x-xa, yb-out.first.first.y ); } else if(out.second.second <= 2*PI) { delta = -fourthquadintersection( out.first.second, make_pair(out.second.first - 2*PI, out.second.second - 2*PI), xa-out.first.first.x, ya-out.first.first.y, xb-out.first.first.x, yb-out.first.first.y ); } else assert(false); tot += delta; } tot *= 100; tot /= (xb - xa) * (yb - ya); cout << fixed << setprecision(12) << tot << "\n"; } void computeArcs(vector& arcs, vector& circles) { for(int i = 0; i < circles.size(); i++) { vector> coverage; coverage.emplace_back(0, 0); coverage.emplace_back(PI/2, 0); coverage.emplace_back(PI, 0); coverage.emplace_back(3*PI/2, 0); coverage.emplace_back(2*PI, 0); for(int j = 0; j < circles.size(); j++) { if(i == j) continue; P ci = P(circles[i].first.x, circles[i].first.y); P cj = P(circles[j].first.x, circles[j].first.y); pair intersections; if(!circleIntersection(ci, cj, circles[i].second, circles[j].second, &intersections)) continue; double t1 = atan2(intersections.first.y - ci.y, intersections.first.x - ci.x); double t2 = atan2(intersections.second.y - ci.y, intersections.second.x - ci.x); if(t1 > t2) t2 += 2 * PI; t1 -= 2 * PI; t2 -= 2 * PI; { assert(t1 <= t2); double avg = (t1+t2)/2; P cand; cand.x = ci.x + circles[i].second * cos(avg); cand.y = ci.y + circles[i].second * sin(avg); // NB: no epsilon because ugh if((cand-cj).dist() > circles[j].second) { swap(t1, t2); t2 += 2 * PI; } } t1 -= 4*PI; t2 -= 4*PI; while(t1 < 2*PI) { double lhs = max(t1, 0.); double rhs = min(t2, 2*PI); if(lhs <= rhs) { coverage.emplace_back(lhs, 1); coverage.emplace_back(rhs, -1); } t1 += 2*PI; t2 += 2*PI; } } double last = 0; sort(coverage.begin(), coverage.end()); int covered = 0; for(int a = 0; a < coverage.size();) { if(a && covered == 0) { arcs.emplace_back(circles[i], make_pair(last, coverage[a].first)); } int j = a; while(j < coverage.size() && coverage[a].first == coverage[j].first) { covered += coverage[j++].second; } last = coverage[a].first; a = j; } assert(covered == 0); } } void solve() { int n, q; cin >> n >> q; vector circles(n); for(int i = 0; i < n; i++) { cin >> circles[i].first.x >> circles[i].first.y >> circles[i].second; } sort(circles.begin(), circles.end(), sortbysize); prune(circles); vector circletranspose = circles; for(int i = 0; i < circletranspose.size(); i++) { swap(circletranspose[i].first.x, circletranspose[i].first.y); } vector arcnormals, arctranspose; computeArcs(arcnormals, circles); computeArcs(arctranspose, circletranspose); while(q--) { qry(arcnormals, arctranspose); } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); solve(); }