Grids |
||
|
||
description |
||
On an 1 × 1 grid,partition the length and width into 50 parts,forming 2500 unit grids with the same size.Now,given n circles with equal radius R on the grid.Find the total number of unit grids which are not covered by any of a circle.
A unit grid is covered by a circle,means that the distance between the center of the unit grid and the center of circle is less or equal R.
|
||
input |
||
There will be multiple test cases.Each line of input contains aInteger n (1≤n≤100) and a decimal R (0.01≤R≤0.1).Follows n lines,each line describe the center of circle i,include two decimal xi, yi (0≤xi, yi≤1).
|
||
output |
||
For each test case output a line,output the number of the points which are not covered.
|
||
sample_input |
||
1 0.02
0.03 0.03
1 0.10
0.952423 0.042419
|
||
sample_output |
||
2495
2454
|
||
hint |
||
|
||
sourc |
思路:填充法,找出每个格子的中心点,看它到每个圆心的距离是不是不超过R是就涂色,最后没涂色的就是答案
#include<iostream> #include<cstring> #include<cmath> #include<cstdio> using namespace std; const int mm=55; const double ex=1e-10; int n; double r,x,y; double z=0.02; bool vis[mm][mm]; double dis(double x1,double y1,double x2,double y2) { double d=(x2-x1)*(x2-x1)+(y2-y1)*(y2-y1); d=sqrt(d); return d; } inline double aabs(double x) { if(x<0)return -x; return x; } void judge(int a,int b) { double x1=(double)a*z+0.01; double y1=(double)b*z+0.01; double d=dis(x1,y1,x,y); if(d<r)vis[a][b]=1; else if(aabs(d-r)<ex) vis[a][b]=1; } int main() { while(cin>>n>>r) { memset(vis,0,sizeof(vis)); for(int i=0;i<n;++i) { cin>>x>>y; for(int i=0;i<50;i++) for(int j=0;j<50;j++) judge(i,j); } int ans=0; for(int i=0;i<50;i++) for(int j=0;j<50;j++) if(vis[i][j]) ++ans; ans=2500-ans; cout<<ans<<"\n"; } }