题解：P4354 [CERC2015] Ice Igloos

思路

First

注意到

1 \le x_i,y_i \le 500

且为整数，考虑从此处入手。

用一个 vector[505][505] 存储每个点圆的半径，并将同一个 vector 里半径从小到大排序。

Second

考虑如何查询每个点上的圆到某条线段的距离是否小于等于半径。

值得注意，这里的距离与以往所说的距离并不完全相同（下面会说到）。

不妨设点

P(x_p,y_p)

和线段

l:y=kx+b(x_1 \le x \le x_2)

，线段端点

A(x_1,y_1)

，

B(x_2,y_2)

，以及从

P

向直线

y=kx+b

作垂线后垂足

H(x_h,y_h)

。

如果

x_h < x_1

或者

x_h > x_2

，那么这里的“距离”就应该定义为

\min(dist(A,P),dist(B,P))

，否则就是

dist(P,l)

。

二分即可。

Third

对于每条直线，分成以下三种情况。

如果这条直线是“横平竖直”的，那么直接统计即可。
如果直线斜率的绝对值小于或者等于 $1$ ，则对于直线上每个点 $G(x_G,y_G)$ ，则可能对答案产生影响的圆心横坐标为 $x_G$ 的只可能圆心纵坐标在 $\left [ \left \lfloor y_G-1 \right \rfloor ,\left \lceil y_G+1 \right \rceil \right ]$ 里的。
如果直线斜率的绝对值大于 $1$ ，那么与上一种情况类似，只需将横纵坐标交换的考虑即可。

代码

CPP

const int N=1e5+5;
const int M=505;
const double eps=1e-9; 
int n,m;
double K,B,X,XX,Y,YY;
double fx(int x){return (x-B)/K;}
double fy(int x){return K*x+B;}
vector<double> G[M][M];
struct Line
{
	double a,b,c;
	Line(int x,int y,int xx,int yy)
	{
		K=1.0*(y-yy)/(x-xx);
		B=y-x*K;
		a=K,b=-1,c=B;
	}
};

double Pow2(double x){return x*x;}
bool check(Line E,int x,int y)
{
	double K1=K,B1=B;
	double K2=-1/K1;
	double B2=(y-K2*x);
	double Px=(B2-B1)/(K1-K2);
	return (Px>=min(X,XX) && Px<=max(X,XX));
}
double Distance(Line E,int x,int y)
{
	return 1.0*fabs(E.a*x+E.b*y+E.c)/sqrt(Pow2(E.a)+Pow2(E.b));
}
double dist(double x,double y,double xx,double yy)
{
	return sqrt(Pow2(xx-x)+Pow2(yy-y));
}
int Get(int x,int y,double r)
{
	return lower_bound(G[x][y].begin(),G[x][y].end(),r)-G[x][y].begin();
}
int Doit(Line E,int x,int y)
{
	if(x<0 || y<0 || x>500 || y>500) return 0;
	if(!G[x][y].size()) return 0;
	if(check(E,x,y)) return G[x][y].size()-Get(x,y,Distance(E,x,y));
	return G[x][y].size()-Get(x,y,min(dist(x,y,XX,YY),dist(x,y,X,Y)));
}
int solvex(Line E,int x,int xx,int y)
{
	int i,ans=0;
	for(i=x;i<=xx;i++)
	ans+=Doit(E,i,y);
	return ans;
}
int solvey(Line E,int x,int y,int yy)
{
	int i,ans=0;
	for(i=y;i<=yy;i++)
	ans+=Doit(E,x,i);
	return ans;
}
int Get_ans(int x,int y,int xx,int yy)
{
	int i,ans=0;
	if(mp(x,y)>mp(xx,yy)) swap(x,xx),swap(y,yy);
	Line E=Line(x,y,xx,yy);
	if(fabs(K)<=1)
	{
		if(mp(x,y)>mp(xx,yy)) swap(x,xx),swap(y,yy);
		X=x,Y=y,XX=xx,YY=yy;
		for(i=x;i<=xx;i++)
		ans+=solvey(E,i,floor(fy(i)-1-eps),ceil(fy(i)+1+eps));
	}
	else
	{
		if(mp(y,x)>mp(yy,xx)) swap(x,xx),swap(y,yy);
		X=x,Y=y,XX=xx,YY=yy;
		for(i=y;i<=yy;i++)
		ans+=solvex(E,floor(fx(i)-1-eps),ceil(fx(i)+1+eps),i);
	}
	return ans;
}
void I_Love_Her_Forever()
{
	int i,j,x,y,xx,yy,q,ans;
	double k;
	n=read();
	for(i=1;i<=n;i++)
	{
		read(x,y);
		scanf("%lf",&k);
		G[x][y].push_back(k);
	}
	for(i=1;i<=500;i++)
	{
		for(j=1;j<=500;j++)
		sort(G[i][j].begin(),G[i][j].end());
	}
	for(q=read();q;q--)
	{
		read(x,y,xx,yy);
		if(x==xx)
		{
			if(mp(y,x)>mp(yy,xx)) swap(x,xx),swap(y,yy);
			for(i=y,ans=0;i<=yy;i++)
			ans+=G[x][i].size();
			write(ans,'\n'); 
			continue;
		}
		if(y==yy)
		{
			if(mp(x,y)>mp(xx,yy)) swap(x,xx),swap(y,yy);
			for(i=x,ans=0;i<=xx;i++)
			ans+=G[i][y].size();
			write(ans,'\n');
			continue;
		}
		write(Get_ans(x,y,xx,yy),'\n');
	}
}

最后放两组数据。

第一组：

CPP

input：
1
284 244 0.62
1
261 269 451 61
  
answer：1

第二组：

CPP

input：
5
2 2 0.99
2 3 0.99
3 2 0.99
3 3 0.99
2 1 0.99
1
2 2 3 3
  
answer：4

题解：P4354 [CERC2015] Ice Igloos

文章操作

思路

First

Second

Third

代码

相关推荐

评论

题解：P4354 [CERC2015] Ice Igloos