/** * Sample solution for How Many Bars in this Town? * Steven J Zeil, 10/10/2010 */ #include #include #include #include #include #include using namespace std; struct Circle { double cx, cy; double r; Circle (double x=0.0, double y=0.0, double r0 = 1.0) : cx(x), cy(y), r(r0) {} bool contains (double x, double y) const; }; bool Circle::contains (double x, double y) const { double dx = x - cx; double dy = y - cy; return dx*dx + dy*dy <= r*r; } bool operator< (const Circle& c1, const Circle& c2) { return c1.r < c2.r; } ostream& operator<< (ostream& out, const Circle& c) { out << "[" << c.cx << " " << c.cy << " " << c.r << "]"; return out; } const double RequiredPrecision = 0.01; const double pi = 3.14159; double rnd () { int multiplier = 10000; return (double)(rand() % multiplier) / ((double)multiplier); } /* * Compute the fraction of the area of city that overlaps * with any of circles 0..numTowers */ double estimateCoveredArea (Circle city, Circle* towers, int numTowers) { if (numTowers == 0) return 0.0; /* * Monte Carlo approach. Generate random points known to lie within * circles[i] and count how many of them do not lie within any of the * other circles. The proportion of that count to the number of * points generated tells us what fraction of the area of circles[i] * is not overlapped. */ const double RequiredPrecision = 0.0001; long attempts = 0; long successes = 0; double lastEstimate = 0.5; double checkpoint = 40 * (int)(1.0 / RequiredPrecision); while (attempts < 1000000) { double x = city.cx + 2.0 * city.r * rnd() - city.r; double y = city.cy + 2.0 * city.r * rnd() - city.r; if (city.contains(x,y)) { // (x,y) lies inside the city ++attempts; bool success = false; for (int j = 0; (!success) && j < numTowers; ++j) success = towers[j].contains(x,y); if (success) { // (x,y) lies within one or more of the tower circles ++successes; } if (attempts == 2*checkpoint) { // Have we reached a stable estimate? double newProportion = (double)(successes) / (double)attempts; cerr << "After " << attempts << " samples, fraction of area " << lastEstimate << " => " << newProportion << endl; if (abs(newProportion - lastEstimate) <= RequiredPrecision*(newProportion+lastEstimate)/2.0) { lastEstimate = newProportion; break; } else { // Need to keep going lastEstimate = newProportion; checkpoint = attempts; } } } } return lastEstimate; } /** * Process a single dataset for the problem. * Return true if successful. Return false if we encounter the * end of input marker or an unreocverable I/O error, */ bool processDataSet (istream& in) { int numCircles; in >> numCircles; if (numCircles == 0) return false; Circle city; Circle* circles = new Circle[numCircles-1]; in >> city.cx >> city.cy >> city.r; for (int i = 0; i < numCircles-1; ++i) { in >> circles[i].cx >> circles[i].cy >> circles[i].r; } double area = estimateCoveredArea (city, circles, numCircles-1); cout << setprecision(2) << fixed << area << endl; return true; } void cellCoverage (istream& in) { bool finished = false; while (!finished) { finished = !processDataSet(in); } } int main (int argc, char** argv) { srand(1231); // Program should normally read from standard in. But // for debugging purposes, it is sometimes easier to // give a file name on the command line. if (argc > 1) { ifstream in (argv[1]); cellCoverage (in); } else cellCoverage(cin); return 0; }