题目大意：
给定n段线段 编号为1~n
接下来m个询问 给定一点
输出离该点最近的线段的最小编号（距离相等时取编号小的)
大致就是
1.坐标范围为（0，2^16-1）
将坐标系划分为2^8*2^8的小块 编号为0~2^8-1
判断线段穿过哪些小块 并用had[ i ][ ]保存穿过 i小块 的所有线段的编号
2.当给定一个点时 找到该点所在的小块
因为最近的线段可能不存在与这个小块
所以暴力 该小块 及其 八联通小块（共九个小块）的线段
#1. 这样可以获得坐标（x，y）所在小块的编号
int getS(double x,double y) { int a=round(x), b=round(y); return (b>>8)*(1<<8)+(a>>8); }
1.round()是一个四舍五入的取整函数 （需要注意的是6.5时得到7或6的概率各50%）
2.(b>>8) 获得纵向该点所在的层数 *(1<<8) 获得该层第一个的编号
(a>>8) 获得横向所在的位置 相加就是 其所在小块的编号了
#2. 计算点到线段的距离
// 点a与点b的距离 double lenPP(P a,P b) { return sqrt( (a-b).dot(a-b) ); } // 点c到线段ab的距离 double lenPS(P a,P b,P c) { if(a==b) return lenPP(a,c); if((b-a).dot(c-a)<0) return lenPP(c,a); else if((b-a).dot(c-b)>0) return lenPP(c,b); else return abs((b-a).det(c-a))/lenPP(b,a); }
需要分三种情况
1. c的垂足在ab上 // 向量ab与ac 点积=0
那么算出 向量ab与ac 组成的平行四边形面积
除以 ab的长度 就可以 得到 c到ab的距离
2. c的垂足在a左侧 // 向量ab与ac 点积<0
ac的长度就是c到ab的距离
3. c的垂足在b右侧 // 向量ab与bc 点积>0
bc的长度就是c到ab的距离
/*
这道题虽然没有出现精度问题
但是计算几何题精度要求高时 下面的地方可能会有问题
结构体重载时 bool operator == (P p) { return x-p.x==0 && y-p.y==0; } getDis()中 if(dis-ansd<0) ... else if(dis-ansd==0 ... ) ...
可以改写为
结构体重载时 bool operator == (P p) { return abs(x-p.x)<eps && abs(y-p.y)<eps; } getDis()中 if(dis-ansd<-eps) ... else if(abs(dis-ansd)<eps ... ) ...
改写规则为
a<0 -> a<-eps
a<=0 -> a<eps
a==0 -> abs(a)<eps
*/
#include <bits/stdc++.h> using namespace std; const int N=(1<<8)+1; const double eps=1e-10; double add(double a,double b) { if(abs(a+b)<eps*(abs(a)+abs(b))) return 0; return a+b; } struct P { double x,y; P(){}; P(double _x,double _y):x(_x),y(_y){}; P operator - (P p) { return P(add(x,-p.x),add(y,-p.y)); } P operator + (P p) { return P(add(x,p.x),add(y,p.y)); } P operator * (double d) { return P(x*d,y*d); } P operator / (double d) { return P(x/d,y/d); } bool operator == (P p) { return x-p.x==0 && y-p.y==0; } double dot (P p) { return add(x*p.x,y*p.y); } double det (P p) { return add(x*p.y,-y*p.x); } }s[10005],e[10005],aim; int n,m,ansi; double ansd; int mov[15]={ -(N-1),-(N-1)-1,-(N-1)+1, // 上 左上 右上 N-1,(N-1)-1,(N-1)+1,-1,1,0 // 下 左下 右下 左 右 中 }; // 点a与点b的距离 double lenPP(P a,P b) { return sqrt( (a-b).dot(a-b) ); } // 点c到线段ab的距离 double lenPS(P a,P b,P c) { if(a==b) return lenPP(a,c); if((b-a).dot(c-a)<0) return lenPP(c,a); else if((b-a).dot(c-b)>0) return lenPP(c,b); else return abs((b-a).det(c-a))/lenPP(b,a); } vector <int> had[N*N]; int getS(double x,double y) { int a=round(x), b=round(y); return (b>>8)*(1<<8)+(a>>8); } void getDis(int S) { for(int i=0;i<had[S].size();i++) { int j=had[S][i]; double dis=lenPS(s[j],e[j],aim); if(dis-ansd<0) ansd=dis, ansi=j; // 若存在更小的距离 else if(dis-ansd==0 && j<ansi) ansi=j; // 距离相等 取更小的编号 } } int main() { while(~scanf("%d%d",&n,&m)) { for(int i=0;i<n;i++) { scanf("%lf%lf%lf%lf",&s[i].x,&s[i].y,&e[i].x,&e[i].y); P v=e[i]-s[i]; // v为s[i]到e[i]的方向向量 v=v/(N-1); // 得到相对于小块长度的单位向量 int a=-1; /// 防止重复保存 for(int j=0;j<N;j++) { P h=s[i]+v*j; // 从 s[i]开始 v方向上 j倍长度 的坐标 int b=getS(h.x,h.y); // 得到所在块 if(b!=a) had[b].push_back(i); // 保存穿过 b小块 的 i线段 a=b; } } while(m--) { scanf("%lf%lf",&aim.x,&aim.y); ansd=1e10; int S=getS(aim.x,aim.y); for(int i=0;i<9;i++) { // 九个小块 int t=S+mov[i]; if(t>=0 && t<N*N) getDis(t); } printf("%d ",ansi+1); } } return 0; }