[乱搞] BZOJ 4434 [Cerc2015]Ice Igloos

#include<cstdio> #include<cstdlib> #include<cmath> #include<algorithm> using namespace std; double r[505][505]; double A,B,C; double K,L; int Count(int x,int y1,int y2){ int ret=0; for (int y=y1;y<=y2;y++) ret+=r[x][y]>0.0 && fabs(A*x+B*y+C)<=r[x][y]; return ret; } int main(){ freopen("t.in","r",stdin); freopen("t.out","w",stdout); int n,Q,x,y; double _r; scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%d%d%lf",&x,&y,&_r),r[x][y]=_r; scanf("%d",&Q); while (Q--){ int x1,x2,y1,y2; scanf("%d%d%d%d",&x1,&y1,&x2,&y2); if (x1>x2 || (x1==x2 && y1>y2)) swap(x1,x2),swap(y1,y2); int ret=0; if (x1==x2){ for (int y=y1;y<=y2;y++) ret+=r[x1][y]>0.0; }else if (y1==y2){ for (int x=x1;x<=x2;x++) ret+=r[x][y1]>0.0; }else{ A=(y2-y1)/sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)); B=(x1-x2)/sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)); C=-(A*x1+B*y1); K=(double)(y2-y1)/(x2-x1); L=y1-K*x1; int l,r,t; if (y2>y1) { l=y1,r=ceil(K*(x1+1)+L-1e-6); ret+=Count(x1,l,r); for (int x=x1+1;x<x2;x++) { t=r,r=ceil(K*(x+1)+L-1e-6); ret+=Count(x,l,r); l=t-1; } ret+=Count(x2,l,r); }else{ r=y1,l=floor(K*(x1+1)+L+1e-6); ret+=Count(x1,l,r); for (int x=x1+1;x<x2;x++){ t=l,l=floor(K*(x+1)+L+1e-6); ret+=Count(x,l,r); r=t+1; } ret+=Count(x2,l,r); } } printf("%d\n",ret); } return 0; }