题解 P3282 【[SCOI2013]泡泡鱼 】

· · 题解

这道题就是一道运用计算几何知识的题，需要并查集维护，思考并不困难，不过因为代码量很大，而且一些精度问题，并不好调试。

对于一开始的预处理，我们可以用并查集维护碰在一起且颜色一样的圆，如果暴力n^2进行枚举合并，对于n小于等于10^5的数据肯定是过不了的，当然我们可以学网上代码用扫描线维护与当前圆横坐标之差不超过2的圆的纵坐标，再二分判断，能做到最坏O(nlogn)的预处理。不过还有另一个办法，常数应该要低一些。 我们可以发现区域边界的坐标很小，我们可以尝试对平面进行划分，可以将平面区域分割成网格，每个格子边长为圆直径的长度。这样只需要枚举当前圆所处格子的周围八个格子里的圆进行合并(枚举量应该不会超过16个)，这样就能很快的进行预处理了。

解决完预处理的问题，现在需要解决发射操作。我们发现数据范围是支持n×q的复杂度的，每一次发射操作我们可以枚举所有圆求出发射的圆撞到它停下来后圆心所处的坐标，进行比较后，就能求出没有墙时会停下的位置。如果不会与其它圆相撞，则会直接撞到墙上，否则再求出撞到墙会停下来的坐标，将其和之前求出的撞到圆停下来的坐标进行比较，便可以知道实际是停在哪个位置的，然后又可以像开始预处理那样枚举周围八个格子进行合并，再判断它所处的并查集里是否有超过2个圆，如果超过了就累计答案，将这些圆打上标记，并把它们所处的方格里将它们自己删除(这里的复杂度稍稍高了一点)，下次枚举就不会考虑这些圆了。

大致思路就是这样，一些小技巧可以看代码，其实代码里有许多地方可以优化，不过本人太懒，也就不想改了。

复杂度大概是O(nlogn+nq)左右。

#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define vector point
using namespace std;
const int N=100010,P=1010;
const double eps=1e-7,pi=acos(-1),inf=999999999;
double w,h,du,l,r;
long long ans,size[N+P];
int n,m,co,flag,fa[N+P],out[N+P],dy[9]={1,1,0,-1,-1,-1,0,1,0},dx[9]={0,1,1,1,0,-1,-1,-1,0};
struct point
{
    double x,y;
    point(double x=0,double y=0):x(x),y(y){}
};
struct area
{
    int num,have[10];
}are[510][1010];
struct circle
{
    point o;int color,x,y;
}cir[N+P];
struct line
{
    point p;vector v;
}sh,up,lef,righ;
vector operator +(vector a,vector b)
{return vector(a.x+b.x,a.y+b.y);}
vector operator -(point a,point b)
{return vector(a.x-b.x,a.y-b.y);}
vector operator *(vector a,double b)
{return vector(a.x*b,a.y*b);}
vector operator /(vector a,double b)
{return vector(a.x/b,a.y/b);}
double cross(vector a,vector b)
{return a.x*b.y-a.y*b.x;}
vector rotate(vector v,double ang)
{return vector(v.x*cos(ang)-v.y*sin(ang),v.x*sin(ang)+v.y*cos(ang));}
double dis(point a,point b)
{return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}
int cmp(double b)
{
    if(fabs(b)<eps)return 0;
    return b<0?-1:1;
}
bool check(point a,point b)
{
    double pd=(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
    if(cmp(pd-4.0)==0)return 1;return 0;
}
int find(int a)
{
    if(fa[a]==a)return a;
    return fa[a]=find(fa[a]);
}
point GLP(line a,line b)
{
    vector u=a.p-b.p;
    double t=cross(b.v,u)/cross(a.v,b.v);
    return a.p+a.v*t;
}
void putin(int a)
{
    //其实这个地方可以不用二分，直接除以2取整就行，要注意负数
    int l=1,r=500,x,y;
    while(l<r)
    {
        int mid=l+r>>1;
        if(cmp(cir[a].o.y-2.0*mid)<=0)r=mid;
        else l=mid+1;
    }
    x=l;l=-500;r=500;
    while(l<r)
    {
        int mid=l+r>>1;
        if(cmp(cir[a].o.x-2.0*mid)<=0)r=mid;
        else l=mid+1;
    }
    y=l+500;are[x][y].have[++are[x][y].num]=a;
    cir[a].x=x;cir[a].y=y;
}
point findpoi(line sh,int now)
{
    line zh;zh.v=rotate(sh.v,pi/2);
    point ans=point(0,0);double minf=inf,len;
    for(int i=1;i<=now;i++)
     if(!out[i])
     {
        zh.p=cir[i].o;
        point poi=GLP(sh,zh);
        len=dis(poi,cir[i].o);
        int pd=cmp(len-2);
        if(pd>0)continue;
        else if(pd<0)
        {
            if(cmp(len)==0)
            {
                vector v=rotate(sh.v,pi);
                poi=cir[i].o+v*2;
                len=dis(poi,point(0,0));
            }
            else
            {
                double cha=acos(len/2.0);
                line l1,l2;l1.p=l2.p=zh.p;
                l1.v=rotate(zh.v,cha);
                l2.v=rotate(zh.v,-cha);
                point poi1=GLP(sh,l1),poi2=GLP(sh,l2);
                double len1=dis(poi1,point(0,0)),
                len2=dis(poi2,point(0,0));
                if(len1<len2)poi=poi1,len=len1;
                else poi=poi2,len=len2;
            }
        }
        else len=dis(poi,point(0,0));
        if(len<minf)minf=len,ans=poi;
     }
    if(minf==inf)flag=0;
    else flag=1;return ans;
}
int main()
{
    scanf("%lf%lf",&w,&h);
    //把边界向内移动一个单位，可以更方便的求出撞到边界后的圆心坐标
    lef.p=point(-w+1,0);righ.p=point(w-1,0);
    lef.v=righ.v=vector(0,1);
    up.p=point(-w,h-1);up.v=vector(1,0);
    l=atan2(h-1,w-1);r=pi-l;
    //求出角度，方便后面判断是撞到哪一面墙
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lf%lf%d",&cir[i].o.x,&cir[i].o.y,&cir[i].color);
        putin(i);fa[i]=i,size[i]=1;
    }
    //预处理
    for(int i=1;i<=n;i++)
     for(int j=0;j<9;j++)
      if(are[cir[i].x+dx[j]][cir[i].y+dy[j]].num)
      {
        int kx=cir[i].x+dx[j],ky=cir[i].y+dy[j];
        for(int k=1;k<=are[kx][ky].num;k++)
        {
            int ci=are[kx][ky].have[k];
            if(check(cir[i].o,cir[ci].o)&&cir[i].color==cir[ci].color)
            {
                int f1=find(i),f2=find(ci);
                if(f1==f2)continue;
                fa[f1]=f2;size[f2]+=size[f1];size[f1]=0;
            }
        }
      }
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%lf%d",&du,&co);
        du=(du*pi)/180.0;
        vector v=vector(1,0);
        sh.v=rotate(v,du);
        point poi1,poi2;
        if(du<=l)poi1=GLP(sh,righ);
        else if(du>l&&du<=r)poi1=GLP(sh,up);
        else poi1=GLP(sh,lef);
        poi2=findpoi(sh,n+i-1);
        //我的查找和判断写的比较麻烦，最好自己思考
        if(!flag)
        {
            cir[n+i].o=poi1;
            cir[n+i].color=co;
            fa[n+i]=n+i;size[n+i]=1;
            putin(n+i);
            continue;
        }
        double l1=dis(point(0,0),poi1),
        l2=dis(point(0,0),poi2);
        if(cmp(l1-l2)<0)
        {
            cir[n+i].o=poi1;
            cir[n+i].color=co;
            fa[n+i]=n+i;size[n+i]=1;
            putin(n+i);
            continue;
        }
        else
        {
            cir[n+i].o=poi2;
            cir[n+i].color=co;
            fa[n+i]=n+i;size[n+i]=1;putin(n+i);
            for(int k=0;k<9;k++)
             if(are[cir[n+i].x+dx[k]][cir[n+i].y+dy[k]].num)
             {
                int kx=cir[n+i].x+dx[k],ky=cir[n+i].y+dy[k];
                for(int q=1;q<=are[kx][ky].num;q++)
                {
                  int ci=are[kx][ky].have[q];
                  if(check(cir[n+i].o,cir[ci].o)&&cir[n+i].color==cir[ci].color)
                  {
                    int f1=find(n+i),f2=find(ci);
                    if(f1==f2)continue;
                    fa[f1]=f2;size[f2]+=size[f1];size[f1]=0;
                  }
                }
             }
            int need=find(n+i);
            if(size[need]<3)continue;
            ans+=size[need]*size[need];size[need]=0;
            for(int k=1;k<=n+i;k++)
             if(find(k)==need)
             {
                int xx=cir[k].x,yy=cir[k].y;
                for(int q=1;q<=are[xx][yy].num;q++)
                 if(are[xx][yy].have[q]==k)
                 {
                    for(int p=q;p<are[xx][yy].num;p++)
                     are[xx][yy].have[p]=are[xx][yy].have[p+1];
                    are[xx][yy].have[are[xx][yy].num]=0;are[xx][yy].num--;
                 }
                out[k]=1;
             }

        }
    }
    printf("%lld\n",ans);
    fclose(stdout);
    return 0;
}