HihoCoder 1834 The Mole ICPC2018 北京网络赛 点到线段最短距离 分块

#include <bits/stdc++.h> //卡精度卡的蛋疼妈蛋
using namespace std;
#define LL long long
const int maxn=1e4+10;
const int blk=256;
vector<int>mp[blk*blk];
#define eps 1e-8
#define inside(x,y) (x>=0&&x<blk&&y>=0&&y<blk)
int vis[maxn];
struct point
{
    double x,y;
    point(double x=0,double y=0):x(x),y(y){}
    void in(){scanf("%lf%lf",&x,&y);}
    double operator ^(const point &a)const{
        return x*a.y-y*a.x;
    }
    double operator *(const point &a)const{
        return x*a.x+y*a.y;
    }
    bool operator ==(const point &a)const{
        return x==a.x&&y==a.y;
    }
    point operator +(const point &a)const {
        return point(x+a.x,y+a.y);
    }
    point operator -(const point &a) const {
        return point(x-a.x,y-a.y);
    }
    double len() {
        return hypot(x,y);
    }
    void getidx(int &a,int &b) { 
        a=x/blk;b=y/blk;
    }
    double dis(point &p) {
        return hypot(x-p.x,y-p.y);
    }
};
struct line
{
    point s,e;
    void init(){s.in();e.in();}
    void getidx(int id){
        int a,b,aa=-1,bb=-1;
        point t=e-s;
        for(int i=0;i<=blk;i++) //把整个平面分成256*256个块 对于每个点查询它最近的9个小块 
        {
            point p=s+point(t.x*i/blk,t.y*i/blk);
            p.getidx(a,b);
            if(a==aa&&b==bb)continue;
            mp[a*blk+b].push_back(id);
            aa=a;bb=b;
        }
    }
    double dis(point &p){
        if(s==e)return s.dis(p); //一直脑瓜想着是点到直线距离 蛋疼 这里线段为点
        if((p-s)*(e-s)<-eps) return s.dis(p); //以s为顶点的钝角
        if((p-e)*(s-e)<-eps) return e.dis(p); //以e为顶点的钝角
        return fabs(((s-p)^(e-p))/(e-s).len()); //面积除以底 
    }//点到线段距离分为上面4种情况
};
line l[maxn];

int main()
{
    #ifdef shuaishuai
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif // shuaishuai
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        l[i].init();
        l[i].getidx(i);
    }
    point p;
    for(int f=m;f>=1;f--)
    {
        p.in();
        int a,b,id=-1;
        p.getidx(a,b);
        double ans=1e18;
        for(int i=-1;i<2;i++)
            for(int j=-1;j<2;j++)
        {
            int x=a+i,y=b+j;
            if(!inside(x,y))continue;
            for(auto c:mp[x*blk+y]){
                if(vis[c]==f)continue;vis[c]=f; //这个标记很重要
                double dis=l[c].dis(p);
                if(dis+eps<ans) ans=dis,id=c;
                else if(fabs(dis-ans)<eps) id=min(id,c);
            }
        }
        if(ans==1e18){
            for(int i=1;i<=n;i++)
            {
                double dis=l[i].dis(p);
                 if(dis+eps<ans) ans=dis,id=i;
                else if(fabs(dis-ans)<eps) id=min(id,i);
            }
        }
        printf("%d\n",id);
    }
    return 0;
}