/* 2004 ACM Mid-Central Regional Programming Contest
Problem F: Blots
by Andy Harrington, Loyola University Chicago
blots.java
Problem:
Distinct circles are specified by their center and radius, positive integers
no more than 1,000,000. No circles are tangent and no three intersect at one
point. They represent the outer boundaries of disks filled with black ink
blots on a white surface that extends beyond all the blots. How many distinct
white regions are determined by these blots?
Parameters are set so double arithmetic accurately determines which circles
intersect and the order of the intersection points around any circle:
circles overlap or are separared by at least one
all angles of intersection on any one circle differ by at least .001 radian
Algorithm:
1. Read all circles (at most 100)
2. Eliminate all circles inside another, and any intersecting no other circle
3. For each circle left
for each previous circle in the list
if they intersect
mark them as in the same component
remove arcs and parts of arcs in the interection with the other circle
link arcs with a common endpoint in the other circle
4. Count boundary components:
For each unmarked arc in each circle
increment the boundary count
follow the links to traverse the whole boundary, marking each arc
5. Return the number of white regions: 1 for the outer white region +
the number of closed arc paths – the number of connected black components.
The final subtraction is because each connected black component has one outer
boundary, which does not contribute to the number of white regions.
Math: If circles
C1 with center (x1, y1) and radius r1
C2 with center (x2, y2) and radius r2
intersect at exactly 2 points and
s is the distance between their centers, let
A = atan2(y2-y1,x2-x1)
B = acos((r1^2 + s^2 - r2^2)/(2*r1*s)) : law of cosines
Then the intersection points on C1 are at angles A+B and A-B.
The angles removed are the interval (A-B, A+B). Always 0 < B < pi.
The part saved from an initial whole circle is [A+B, A-B + 2pi].
After considering the first intersection of C1, the saved part lies in
some interval of length less than 2pi. We keep that situation as follows:
We maintain the arc endpoint angles in an increasing sequence, from a to b,
with a < b <= a + 2pi - .001. Let k = a - .001/2, then the endpoint angle
also lie in increasing sequence in the range I = [k, k+2pi) and there is no
boundary point at k or k+2pi. The intersection interval with another circle
may be stated initially as [c', d'], which can be shifted by a multiple of 2pi
to [c, d] so c is in I. If d is in I, then there is no issue of distinctions
mod 2pi. If d is not in I, then the part to be removed can be considered in
two parts: [k, d-2pi] and [c, k+2pi), both within I for easy comparisons.
When d > k+2pi, the program actually replaces k+2pi with d, since nothing more
is removed.
By uncommenting the display line, the input can be viewed graphically.
In that version, closing any one display window terminates the program.
To see other displays, working backwards through the datasets, move or
minimize the one on top. The displays may be resized which rescales and can
show more detail. The display uses the included file DisplayCircles.java.
*/
import java.io.*;
import java.util.*;
public class blots {
static final int MAX_CIRCLES = 100;
static final double PI = Math.PI;
static final double ANG_CONV = 1.0; // make it 180/PI to view in degrees
static final double PERIOD = ANG_CONV*PI*2;
static final double MIN_SEP = 0.001*ANG_CONV;
static Disk[] disk = new Disk[MAX_CIRCLES];
static int nDisks;
static int dataSet = 0;
public static void main(String[] arg) {
String FILE = "blots";
ACMIO in = new ACMIO(FILE + ".in");
PrintWriter out = null;
try {
out = new PrintWriter(
new BufferedWriter(
new FileWriter(FILE + ".out")));
} catch(Exception e) {
System.out.println("can't open output");
}
nDisks = in.intRead();
int i, j;
while ( nDisks != 0) { // one dataset per loop
dataSet++;
for (i = 0; i < nDisks; i++) // get whole dataset
disk[i] = new Disk(in.intRead(), in.intRead(), in.intRead(), i);
dataIntegrityCheck(); // This line is not needed in student solutions
// UNCOMMENT the next line to see all the datasets displayed graphically
// (new DisplayCircles(disk, nDisks, dataSet)).setVisible(true);
i = 0;
while (i < nDisks) // remove nested and isolated disks from the list
if (inside(i) || outside(i)) {
nDisks--;
disk[i] = disk[nDisks];
}
else
i++;
// now each circle intersects at least one other
int totComponents = nDisks;
for (i = 1; i < nDisks; i++) { // process intersecions
Disk c1 = disk[i];
for (j = 0; j < i; j++) {
Disk c2 = disk[j];
double d = c1.centerDist(c2);
if (d > c1.r + c2.r)
continue; // no intersection for these two disks
if (c2.component != c1.component) { // merge components
totComponents--;
int toChange = c2.component;
for (int k = 0; k < i; k++) // quick and dirty merging
if (disk[k].component == toChange)
disk[k].component = c1.component;
}
Arc[] startEnd1 = c1.reduceArcs(c2);
Arc[] startEnd2 = c2.reduceArcs(c1);
if (startEnd1[1] != null) // link intersecting arcs
startEnd1[1].next = startEnd2[0];
// This may set a next field to null if c has already been intersected
// with a circle c3, removing the point. Untimately that endpoint
// will also be removed from c1, when c3 or some other circle gets
// intersected with c1. The final boundary arcs left will share
// endpoints with other arcs that are left, and none of their next
// fields will be null.
if (startEnd2[1] != null)
startEnd2[1].next = startEnd1[0];
} // inner disk loop
} // outer disk loop
// traverse and count all the boundary paths
int boundaryCount = 0;
for (i = 0; i < nDisks; i++)
for(j = disk[i].arcs.size()-1; j >= 0; j--) {
Arc arc = (Arc)disk[i].arcs.get(j);
if (!arc.counted) {
boundaryCount++;
do {
arc.counted = true;
arc = arc.next;
} while (!arc.counted);
}
}
out.println(1 + boundaryCount - totComponents);
nDisks = in.intRead();
} // end of dataset
out.close();
}
// true if disk[n] is totally inside any other disk
static boolean inside(int n) {
Disk c = disk[n];
for (int i = 0; i < nDisks; i++)
if (i != n && c.centerDist(disk[i]) + c.r < disk[i].r)
return true;
return false;
}
// true if disk[n] is totally outside every other disk
static boolean outside(int n) {
Disk c = disk[n];
for (int i = 0; i < nDisks; i++)
if (i != n && c.centerDist(disk[i]) < c.r + disk[i].r)
return false;
return true;
}
//-------------------------------------------------------------------------
static class Arc {
double a1, a2; // arc includes angles [a1, a2]
Arc next; // arc on another circle with the point at a2 of this arc as initial point
boolean counted; // true if this arc has been traversed in a final boundary
Arc(double ang1, double ang2, Arc next) {
a1 = ang1;
a2 = ang2;
this.next = next;
}
} // end of inner class Arc
//-------------------------------------------------------------------------
public static class Disk {
int component;
double x, y, r;
ArrayList arcs; // arcs in boundary
// null if whole circle; empty if no boundary left
// all angles in increasing order
// angle of end of final arc < PERIOD + start of initial arc
Disk(double xx, double yy, double rr, int comp) {
x = xx;
y = yy;
r = rr;
component = comp;
}
double centerDist(Disk c) { // distance between centers
double dx = c.x - x, dy = c.y - y;
return Math.sqrt(dx * dx + dy * dy);
}
// angle range in this circle of the intersection with c
double[] angRange(Disk c) {
// Apply law of cosines to the triangle whose vertices are
// an intersection point and both centers.
double d = centerDist(c);
double midAngle = Math.atan2(c.y - y, c.x - x) * ANG_CONV;
double halfAngle = Math.acos((r*r + d*d - c.r*c.r)/(2*r*d)) * ANG_CONV;
return new double[] {midAngle - halfAngle, midAngle + halfAngle};
}
// Remove from the remaining boundary arcs on this circle everything inside
// the intersection with c.
// Return the arcs whose initial or final point intersects c.
// Return null where the intersection point with c is not in a boundary arc.
Arc[] reduceArcs(Disk c) {
// find the arc of intersection: the part to delete
double[] ang = angRange(c);
if (arcs == null) { // still whole circle
arcs = new ArrayList();
Arc arc = new Arc(ang[1], ang[0] + PERIOD, null); //complement of gap
arcs.add(arc);
return new Arc[] {arc, arc}; // both ends are intersection points
}
// this boundary has 0 or more arcs left
Arc[] startEnd = new Arc[2]; // for arcs with start or end intersection pt
// find range for all arc angles a: branchCut < a < branchCut + PERIOD
double branchCut = ((Arc)arcs.get(0)).a1 - MIN_SEP/2;
double branchShift = PERIOD*Math.floor((ang[0]-branchCut)/PERIOD);
ang[0] -= branchShift; // now in [branchCut, branchCut+PERIOD)
ang[1] -= branchShift; // ang[1] right in relation to ang[0]
if (ang[1] > branchCut + PERIOD)
// The full arc to be deleted wraps and is split in two at branchCut.
// No arc is assigned to startEnd[1],
// since the branchCut angles were arranged to be in no arc.
cutGap(branchCut, ang[1] - PERIOD, startEnd);
cutGap(ang[0], ang[1], startEnd);
return startEnd;
}
// Remove from boundary arcs any angle a in (startDel, endDel).
// This interval is set so no further modifications mod 2pi are needed.
// If the angle startDel becomes the final pt of an arc, startEnd[1] is
// set to the arc; similarly for startEnd[0] if endDel is an intial pt.
void cutGap(double startDel, double endDel, Arc[] startEnd) {
if (arcs.isEmpty())
return;
int i = 0;
Arc arc = (Arc)arcs.get(i);
while(arc.a2 < startDel) { // skip what is completely before the deletion
i++;
if(i == arcs.size())
return;
arc = (Arc)arcs.get(i);
}
if (arc.a1 < startDel) { // chop starting in arc, into 1 or 2 pieces
double oldA2 = arc.a2;
arc.a2 = startDel;
startEnd[1] = arc;
if (endDel < oldA2) { // middle to be removed from arc
// It is important that the kept and modified arc is the one that
// includes the initial point and the new arc is after it, so the
// linked list can be maintained.
Arc newArc = new Arc(endDel, oldA2, arc.next);
startEnd[0] = newArc;
arcs.add(i+1, newArc);
return; // came to the end of the deletion
}
i++; // pass this (single if the code reached here) chopped arc
if (i == arcs.size())
return;
arc = (Arc)arcs.get(i);
}
while(arc.a2 < endDel) { // arcs to totally remove
arcs.remove(i); // quick to code and fast enough
if(i == arcs.size())
return;
arc = (Arc)arcs.get(i); // next arc after renumbering
}
// at the last arc that might be affected -- possibly chop its start
if (arc.a1 < endDel) {
arc.a1 = endDel;
startEnd[0] = arc;
}
}
} // end of inner class Disk
// The rest is judge's data test, not needed in a student solution -----------
static void dataIntegrityCheck() {
double[] a = new double[2 * MAX_CIRCLES + 1];
for (int i = 0; i < nDisks; i++) {
Disk c1 = disk[i];
int nAng = 0;
for (int j = 0; j < nDisks; j++) {
if (i == j)
continue;
Disk c2 = disk[j];
double d = c1.centerDist(c2);
if (i < j && Math.abs(c1.r + c2.r - d) < 1.2) // strengthen restrictions
System.out.println("Bad radii: " + dataSet + " " + i + " " + j);
if (d > c1.r + c2.r)
continue; // no intersection for these two circles
if (d == 0.0 && c1.r == c2.r)
System.out.println("Duplicates: " + dataSet + " " + i + " " + j);
double[] ang = c1.angRange(c2); // abs val of angles < 1.5*PERIOD
for (int k = 0; k < 2; k++) { // make -PERIOD/2 < angle <= PERIOD/2
if (ang[k] <= -PERIOD/2)
ang[k] += PERIOD;
if (ang[k] > PERIOD/2)
ang[k] -= PERIOD;
a[nAng] = ang[k];
nAng++;
}
}
Arrays.sort(a, 0, nAng);
a[nAng] = a[0] + PERIOD; // so can compare on either end
for (; nAng > 0; nAng--)
if (a[nAng] - a[nAng - 1] <= MIN_SEP*1.2) // strengthen restrictions
System.out.println("close intersections: " + dataSet + " " + i);
}
} // end of judge's data integrity check
} // end of class blots