题解：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

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

代码

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');
    }
}

最后放两组数据。

第一组：

input：
1
284 244 0.62
1
261 269 451 61

answer：1

第二组：

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