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

#include  //卡精度卡的蛋疼妈蛋
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=0&&yint 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 shuaishuaifreopen("in.txt","r",stdin);freopen("out.txt","w",stdout);#endif // shuaishuaiint 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+epsc;else if(fabs(dis-ans)min(id,c);}}if(ans==1e18){for(int i=1;i<=n;i++){double dis=l[i].dis(p);if(dis+epsi;else if(fabs(dis-ans)min(id,i);}}printf("%d\n",id);}return 0;
}

转载于:https://www.cnblogs.com/polya/p/9808049.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！