/** @JUDGE_ID: GOKURI_SQUEEZE ??? C++ */ #include #include #include #include #include #include #include #include #include using namespace std; #define FNAME "circle.txt" #define cin fin const int NUM = 1000000; const double PI = 3.1415926535; double AREA_0; double AREA_1; double AREA_2; double AREA_3; double AREA_4; double area1() { double ret = 0.0; for (int i = 0; i < NUM; ++i) { double h = 0.5 / NUM; double x = 0.5 + h * i; double d = sqrt(1 - x * x) * h; ret += d; } return 4 * ret; } double area2() { const double S2 = sqrt(0.5); double ret = 0.0; for (int i = 0; i < NUM; ++i) { double h = 1.0 / NUM; double x = h * i; // double d = sqrt(1 - x * x) * h; double d = (sqrt(1 - x * x) - (1 - sqrt(1 - (x - 1) * (x - 1)))) * h; ret += d; } return ret; } double area3() { return (AREA_2 + AREA_4) / 2; #if 0 const double S2 = sqrt(0.5); double ret = 0.0; for (int i = 0; i < NUM; ++i) { double h = (S2 - 0.5) / NUM; double x = 0.5 + h * i; double d = (2 * sqrt(1 - x * x) - 1.0) * h; ret += d; } for (int i = 0; i < NUM; ++i) { double h = 0.5 / NUM; double x = h * i; double d = (sqrt(1 - x * x) - (1 - sqrt(1 - (x - 1) * (x - 1)))) * h; ret += d; } return ret; #endif } double area4() { const double S2 = sqrt(0.5); double ret = 0.0; for (int i = 0; i < NUM; ++i) { double h = (S2 - 0.5) / NUM; double x = 0.5 + h * i; double d = (sqrt(1 - x * x) - 0.5) * h; ret += d; } return 4 * ret; } double solve(const set > & points) { int n0 = 0, n1 = 0, n2 = 0, n3 = 0, n4 = 0; for (set >::const_iterator it = points.begin(); it != points.end(); ++it) { int i = it->first; int j = it->second; ++n0; bool ipjp = points.find(make_pair(i + 1, j + 1)) != points.end(); bool imjp = points.find(make_pair(i - 1, j + 1)) != points.end(); bool ijp = points.find(make_pair(i , j + 1)) != points.end(); bool ipj = points.find(make_pair(i + 1, j )) != points.end(); if (ijp) { ++n1; } if (ipj) { ++n1; } if (ipjp) { ++n2; } if (imjp) { ++n2; } if (ijp && ipj) { ++n3; } if (ijp && ipjp) { ++n3; } if (ipj && ipjp) { ++n3; } if (ipj && imjp) { ++n3; } if (ijp && ipj && ipjp) { ++n4; } } #if 0 cout << n0 << ' ' << n1 << ' ' << n2 << ' ' << n3 << ' ' << n4 << ' ' << endl; #endif return n0 * AREA_0 - n1 * AREA_1 - n2 * AREA_2 + n3 * AREA_3 - n4 * AREA_4; } int main() { ifstream fin(FNAME); if(!fin) return -1; AREA_0 = PI; AREA_1 = area1(); AREA_2 = area2(); AREA_4 = area4(); AREA_3 = area3(); #if 0 cout << AREA_1 << ' ' << AREA_2 << ' ' << AREA_3 << ' ' << AREA_4 << ' ' << endl; #endif int N; int test = 0; while (cin >> N, N) { set > points; // vector > points(202, vector(202)); for (int i = 0; i < N; ++i) { int x, y; cin >> x >> y; points.insert(make_pair(x, y)); // points[x][y] = 1; } double area = solve(points); char buf[32]; sprintf(buf, "%.4f", area); cout << "Data set #" << (++test) << ": "; cout << "Total area = " << buf << " square meters." << endl; } return 0; }