// David Poeschl import java.util.*; public class ChampagneDavid { public static void main(String[] args) { Scanner scan = new Scanner(System.in); List glasses = new ArrayList<>(); int numGlasses = scan.nextInt(); for (int i = 0; i < numGlasses; i++) glasses.add(new Glass(scan.nextInt(), scan.nextInt(), scan.nextInt(), scan.nextInt(), scan.nextInt())); scan.close(); solve(glasses); } private static void solve(List glasses) { if (glasses.size() == 1) { System.out.printf("%.2f", glasses.get(0).v / 100d); System.out.println(); return; } Collections.sort(glasses); for (Glass sourceGlass : glasses) for (Glass targetGlass : glasses) if (sourceGlass.z > targetGlass.z) sourceGlass.handleOverflow(targetGlass); List reachedGlasses = new ArrayList<>(); for (Glass g : glasses) for (GlassArcTuple t : g.overflows) if (!reachedGlasses.contains(t.glass)) reachedGlasses.add(t.glass); if (reachedGlasses.size() != glasses.size() - 1) { System.out.println("Invalid"); return; } glasses.get(0).fillRate = 100; double currentTime = 0; while (anyGlassesNotFilled(glasses)) { List fillingGlasses = getFillingGlasses(glasses); List nextFullGlasses = new ArrayList<>(); double nextFullGlassTimeFromNow = Double.MAX_VALUE; for (Glass fillingGlass : fillingGlasses) { double timeToFill = fillingGlass.timeUntilFill(); if (timeToFill < nextFullGlassTimeFromNow) { nextFullGlassTimeFromNow = timeToFill; nextFullGlasses = new ArrayList<>(); nextFullGlasses.add(fillingGlass); } else if (timeToFill == nextFullGlassTimeFromNow) nextFullGlasses.add(fillingGlass); } currentTime += nextFullGlassTimeFromNow; for (Glass glass : glasses) { glass.advanceTime(nextFullGlassTimeFromNow); } for (Glass nextFullGlass : nextFullGlasses) { nextFullGlass.fillAmount = nextFullGlass.v; } for (Glass nextFullGlass : nextFullGlasses) { nextFullGlass.overflowAndUpdateDependentFillRates(nextFullGlass.fillRate); } for (Glass nextFullGlass : nextFullGlasses) { nextFullGlass.fillRate = 0; } } System.out.printf("%.2f", currentTime); System.out.println(); } private static boolean anyGlassesNotFilled(List glasses) { for (Glass g : glasses) if (g.fillAmount != g.v) return true; return false; } private static List getFillingGlasses(List glasses) { List result = new ArrayList<>(); for (Glass g : glasses) if (g.fillRate > 0) result.add(g); return result; } private static class Glass implements Comparable { public int x; public int y; public int z; public int r; public int v; public List spillage; public List overflows; public double fillRate; public double fillAmount; public Glass(int x, int y, int z, int r, int v) { this.x = x; this.y = y; this.z = z; this.r = r; this.v = v; spillage = new ArrayList(); spillage.add(new Arc(0, 2 * Math.PI)); overflows = new ArrayList(); } public void handleOverflow(Glass target) { if (spillage.size() == 0) return; if (x == target.x && y == target.y && r == target.r) return; double centerDistanceSquared = Math.pow(x - target.x, 2) + Math.pow(y - target.y, 2); if (centerDistanceSquared >= Math.pow(r + target.r, 2)) return; if (centerDistanceSquared <= Math.pow(r - target.r, 2)) { if (target.r > r) { for (Arc spill : spillage) { overflows.add(new GlassArcTuple(target, spill)); } spillage.clear(); } return; } double d = Math.sqrt(centerDistanceSquared); double d1 = (Math.pow(r, 2) - Math.pow(target.r, 2) + Math.pow(d, 2)) / (2 * d); double h = Math.sqrt(Math.pow(r, 2) - Math.pow(d1, 2)); double midpointX = x + (d1 * (target.x - x)) / d; double midpointY = y + (d1 * (target.y - y)) / d; double intersection1x = midpointX + (h * (target.y - y)) / d; double intersection1y = midpointY - (h * (target.x - x)) / d; double intersection2x = midpointX - (h * (target.y - y)) / d; double intersection2y = midpointY + (h * (target.x - x)) / d; double angle1 = calculateAngleOfPointClockwiseFromVertical(intersection1x, intersection1y); double angle2 = calculateAngleOfPointClockwiseFromVertical(intersection2x, intersection2y); if (angle1 > angle2) { double temp = angle1; angle1 = angle2; angle2 = temp; } double averageAngleFromVertical = (angle1 + angle2) / 2; double regularCoordinatesAngle = 2 * Math.PI - (averageAngleFromVertical - Math.PI / 2); double averagePointX = x + r * Math.cos(regularCoordinatesAngle); double averagePointY = y + r * Math.sin(regularCoordinatesAngle); double distanceFromAveragePointToTargetCenter = Math.sqrt(Math.pow(averagePointX - target.x, 2) + Math.pow(averagePointY - target.y, 2)); if (distanceFromAveragePointToTargetCenter < target.r) { handleOverflowArc(new Arc(angle1, angle2), target); } else { handleOverflowArc(new Arc(angle2, 2 * Math.PI), target); handleOverflowArc(new Arc(0, angle1), target); } } private double calculateAngleOfPointClockwiseFromVertical(double x, double y) { double dx = this.x - x; double dy = this.y + r - y; double dSquared = Math.pow(dx, 2) + Math.pow(dy, 2); double angle = Math.acos((dSquared - 2 * Math.pow(r, 2)) / (-2 * Math.pow(r, 2))); if (x < this.x) angle = 2 * Math.PI - angle; return angle; } private void handleOverflowArc(Arc arc, Glass target) { List newSpillage = new ArrayList(); for (Arc spill : spillage) { if (spill.beta <= arc.alpha) { newSpillage.add(spill); continue; } else if (spill.alpha >= arc.beta) { newSpillage.add(spill); continue; } double overlapAlpha = Math.max(spill.alpha, arc.alpha); double overlapBeta = Math.min(spill.beta, arc.beta); overflows.add(new GlassArcTuple(target, new Arc(overlapAlpha, overlapBeta))); if (spill.alpha < arc.alpha) { newSpillage.add(new Arc(spill.alpha, arc.alpha)); } if (spill.beta > arc.beta) { newSpillage.add(new Arc(arc.beta, spill.beta)); } } spillage = newSpillage; } public double timeUntilFill() { return (v - fillAmount) / fillRate; } public void advanceTime(double nextFullGlassTimeFromNow) { if (fillRate > 0) { fillAmount += fillRate * nextFullGlassTimeFromNow; } } public void overflowAndUpdateDependentFillRates(double fillRate) { for (GlassArcTuple overflow : overflows) { Glass targetGlass = overflow.glass; double circlePercentage = overflow.arc.CirclePercentage(); double overflowRate = circlePercentage * fillRate; if (targetGlass.fillAmount != targetGlass.v) { targetGlass.fillRate += overflowRate; } else { targetGlass.overflowAndUpdateDependentFillRates(overflowRate); } } } @Override public int compareTo(Glass g) { return g.z - z; } } private static class Arc { public double alpha; public double beta; public Arc(double alpha, double beta) { this.alpha = alpha; this.beta = beta; } public double CirclePercentage() { return (beta - alpha) / (2 * Math.PI); } } private static class GlassArcTuple { public Glass glass; public Arc arc; public GlassArcTuple(Glass glass, Arc arc) { this.glass = glass; this.arc = arc; } } }