很妙的题!!!
开始以为好麻烦滴说,以为还要求圆面积并,再和正方形求交什么的,瞟了下讨论,有个说时间复杂度1000^2,思路瞬间明朗。。
我好笨。。。精度限制不高,最裸的枚举都能过。。。把1*1的正方形划分成1000*1000个点,然后找在圆内的点数即可。
精度太松了,100*100都能过。。
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <limits.h>
#include <string.h>
#include <string>
#include <algorithm>
#define MID(x,y) ( ( x + y ) >> 1 )
#define L(x) ( x << 1 )
#define R(x) ( x << 1 | 1 )
#define FOR(i,s,t) for(int i=s; i<t; i++)
#define BUG puts("here!!!")
#define STOP system("pause")
using namespace std;
const int MAX = 15;
struct circle {
double x, y, r;
void get()
{
scanf("%lf%lf%lf", &x, &y, &r);
}
};
circle c[MAX];
bool incircle(double x, double y, circle c)
{
return (x - c.x)*(x - c.x)+(y - c.y)*(y - c.y) <= c.r * c.r;
}
bool check(double x, double y, int n)
{
FOR(i, 0, n)
if( incircle(x, y, c[i]) )
return true;
return false;
}
int main()
{
int n;
while( ~scanf("%d", &n) )
{
FOR(i, 0, n)
c[i].get();
int sum = 0;
for(double i=0; i<=1; i+=0.001)
for(double k=0; k<=1; k+=0.001)
if( check(i, k, n) )
sum++;
printf("%.6lf\n", sum/10000.0);
}
return 0;
}