import java.awt.geom.Point2D; import java.io.File; import java.io.FileNotFoundException; import java.util.LinkedList; import java.util.Scanner; /** * Sample solution for Cell Coverage * @author zeil * */ public class cellCoverage { class Circle { public Point2D.Double center; public double radius; public Circle (double x, double y, double r) { center = new Point2D.Double(x, y); radius = r; } public double area() { return Math.PI * radius * radius; } } private Circle city; private Circle[] towers; public cellCoverage(int n, Scanner in) { int nTowers = n - 1; towers = new Circle[nTowers]; double x, y, r; x = in.nextDouble(); y = in.nextDouble(); r = in.nextDouble(); city = new Circle (x, y, r); for (int i = 0; i < nTowers; ++i) { x = in.nextDouble(); y = in.nextDouble(); r = in.nextDouble(); towers[i] = new Circle (x, y, r); } } public static void main (String[] args) throws FileNotFoundException { Scanner input; if (args.length > 0) { input = new Scanner (new File(args[0])); } else { input = new Scanner(System.in); } int N = input.nextInt(); while (N > 0) { new cellCoverage(N, input).solve(); N = input.nextInt(); } } private void solve() { double towerAreas = 0.0; for (int i = 0; i < towers.length; ++i) towerAreas += marginalAreaOf (i); double fractionCovered = towerAreas / city.area(); System.out.format("%.2f%n", fractionCovered); } /** * The workhorse of this program: Use numerical integration to estimate the * area of towers[i] that is not overlapped with towers[i+1..] but that does * overlap with city. * * @param towerNum which tower to compute the marginal area of * @return area contributed by this tower to the total coverage */ private double marginalAreaOf(int towerNum) { // Numerical integration in polar coordinates // Integrate 0.5r^2(d theta) from theta=0 to theta=2*Pi double TwoPi = 2.0 * Math.PI; int nSteps = 10000; double dTheta = TwoPi / (double)nSteps; double integral = 0.0; for (int step = 0; step < nSteps; ++step) { double theta = ((double)step) * dTheta; double r = clippedR(towerNum, theta); integral += r*r*dTheta/2.0; } return integral; } // Compute the distance from the center of the indicated tower // that we can move in direction theta until first encountering // either the radius of this tower, of any of the succeeding towers, or // of the enclosing city. // private double clippedR(int towerNum, double theta) { double r = towers[towerNum].radius; double xc = towers[towerNum].center.x; double yc = towers[towerNum].center.y; LinkedList intersections = new LinkedList(); getIntersectionsWithCircle(xc, yc, theta, city, intersections); for (int t = towerNum+1; t < towers.length; ++t) getIntersectionsWithCircle(xc, yc, theta, towers[t], intersections); for (Point2D p: intersections) { double r2 = directionalDistance (xc, yc, theta, p); if (r2 >= 0.0 && r2 < r) r = r2; } return r; } private double directionalDistance(double xc, double yc, double theta, Point2D p) { double d = p.distance(xc, yc); double x2 = xc + Math.cos(theta); double y2 = yc + Math.sin(theta); double dotProduct = (x2 - xc) * (p.getX() - xc) + (y2 - yc) * (p.getY() - yc); if (dotProduct < 0.0) d = -d; return d; } private void getIntersectionsWithCircle(double x1, double y1, double theta, Circle c, LinkedList intersections) { // Shift to circle-centered coordinates x1 -= c.center.x; y1 -= c.center.y; // Find another point on the line double x2 = x1 + Math.cos(theta); double y2 = y1 + Math.sin(theta); // Solve for intersection with c double dx = x2 - x1; double dy = y2 - y1; double drsq = dx*dx + dy * dy; double D = x1 * y2 - x2 * y1; double delta = c.radius*c.radius * drsq - D*D; if (delta >= 0.0) { double t = Math.sqrt(delta); double sign = (dy < 0) ? -1.0 : 1.0; double x = (D*dy + sign * dx * t) / drsq; double y = (-D*dx + Math.abs(dy) * t) / drsq; // Add 1st intersection point to list intersections.add(new Point2D.Double(x+c.center.x,y+c.center.y)); x = (D*dy - sign * dx * t) / drsq; y = (-D*dx - Math.abs(dy) * t) / drsq; // Add 2nd intersection point to list (might be same as first) intersections.add(new Point2D.Double(x+c.center.x,y+c.center.y)); } } }