锐客网

  1. 首页 > it技术 > >

[WC2013]平面图——平面图点定位


[WC2013]平面图
码农题
平面图点定位：
【[WC2013]平面图——平面图点定位】1.平面图转对偶图：[HNOI2016]矿区
2.扫描线点定位
把所有的顶点和询问点排序，扫描线
每个边在fr的位置加入，to的位置删除，竖直直线不要
用set维护当前的线段，kx+b形式
全局变量X放入重载小于号的比较函数，便于直接比较
到了询问点，直接查询上方第一个线段，得到这个线段所属对偶图新点的编号，即可得到这个询问点的位置
（需要在线就可持久化平衡树吧。。）

trick：
A.可以把询问点当做：0*x+p[i].y，直接查询即可
B.避免插入删除时候纵坐标一样的麻烦，X+=0.1后插入，X-=0.1后删除
C.询问上方第一个线段，（我的对偶图内部是顺时针），所以保留to的横坐标比fr的大的边即可，省去了线段重合的麻烦

然后求MST之后倍增找到链上最大值即可

实现
扫描线时候：
直接开vector把涉及的插入线段，删除线段，询问点直接塞进去，直接查询即可
可能有重边！
这个时候必须保留最小值，先把所有边sort之后再加入。
但是注意：b[++m]=bian(...,...,...m)bian构造函数传进去的m还是之前的m！并没有++m
所以把++m放外面先做
另外，总涉及点数是3*n的。
[WC2013]平面图——平面图点定位
文章图片

大致解释
code：并不能过UOJhack数据
[WC2013]平面图——平面图点定位
文章图片
[WC2013]平面图——平面图点定位
文章图片

#include #define reg register int #define il inline #define fi first #define se second #define mk(a,b) make_pair(a,b) #define numb (ch^'0') #define pb push_back #define solid const auto & #define enter cout< using namespace std; typedef long long ll; templateil void rd(T &x){ char ch; x=0; bool fl=false; while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true); for(x=numb; isdigit(ch=getchar()); x=x*10+numb); (fl==true)&&(x=-x); } templateil void output(T x){if(x/10)output(x/10); putchar(x%10+'0'); } templateil void ot(T x){if(x<0) putchar('-'),x=-x; output(x); putchar(' '); } templateil void prt(T a[],int st,int nd){for(reg i=st; i<=nd; ++i) ot(a[i]); putchar('\n'); }namespace Miracle{ const int N=1e5+5; const int inf=0x3f3f3f3f; int n,m,q; struct lj{ int x,y,z; bool friend operator <(lj a,lj b){ return a.zexi; //pre---------------------------------------------------------------------------// struct po{ double x,y; po(){} po friend operator -(po a,po b){return po(a.x-b.x,a.y-b.y); } po(double xx,double yy){ x=xx; y=yy; } bool friend operator <(po a,po b){ return a.xto[N]; int nxt[2*N]; int nc; //newcur int be[2*N]; int findnxt(const line &A,const int &id){ int lp=upper_bound(to[id].begin(),to[id].end(),A)-to[id].begin(); if(lp==to[id].size()) lp=0; return to[id][lp].id; } struct edge{ int x,y,val; bool friend operator <(edge a,edge b){ return a.val=0; --j){ if(dep[fa[x][j]]>=dep[y]){ ret=max(ret,mx[x][j]); x=fa[x][j]; } } if(x==y) return ret; for(reg j=17; j>=0; --j){ if(fa[x][j]!=fa[y][j]){ ret=max(ret,max(mx[x][j],mx[y][j])); x=fa[x][j],y=fa[y][j]; } } ret=max(ret,max(mx[x][0],mx[y][0])); return ret; } //dfs&&lca------------------------------------------------------------------------// double X; struct bian{ double k,b; int id; bian(){} bian(double kk,double bb,double dd){ k=kk; b=bb; id=dd; } double f(){return k*X+b; } bool friend operator <(bian A,bian B){ return A.f()s; int rk[3*N]; bool cmp(int x,int y){ return p[x]qs[3*N]; vectordel[3*N]; vectorins[3*N]; int qa[N],qb[N]; int in[3*N]; int main(){ rd(n); int lp; rd(lp); int x,y; for(reg i=1; i<=n; ++i){ rd(x); rd(y); p[++num].x=x; p[num].y=y; } for(reg i=1; i<=lp; ++i){ rd(name[i].x); rd(name[i].y); rd(name[i].z); if(name[i].x>name[i].y) swap(name[i].x,name[i].y); }sort(name+1,name+lp+1); m=-1; //warning!! m=-1 for(reg i=1; i<=lp; ++i){ pii tmp=mk(name[i].x,name[i].y); if(exi.count(tmp)) continue; exi[tmp]=1; ++m; b[m]=line(name[i].x,name[i].y,name[i].z,m); to[name[i].x].push_back(b[m]); ++m; b[m]=line(name[i].y,name[i].x,name[i].z,m); to[name[i].y].push_back(b[m]); } trans(); kruskal(); dfs(1,1); for(reg j=1; j<=17; ++j){ for(reg i=1; i<=nc; ++i){ fa[i][j]=fa[fa[i][j-1]][j-1]; mx[i][j]=max(mx[i][j-1],mx[fa[i][j-1]][j-1]); } } rd(q); for(reg i=1; i<=q; ++i){ po tmp; scanf("%lf",&tmp.x); scanf("%lf",&tmp.y); ++num; p[num]=tmp; qa[i]=num; scanf("%lf",&tmp.x); scanf("%lf",&tmp.y); ++num; p[num]=tmp; qb[i]=num; qs[qa[i]].push_back(qa[i]); qs[qb[i]].push_back(qb[i]); } for(reg i=1; i<=num; ++i) rk[i]=i; sort(rk+1,rk+num+1,cmp); for(reg i=0; i<=m; ++i){ if(p[b[i].fr].x
View Code
转载于:https://www.cnblogs.com/Miracevin/p/10898517.html

    推荐阅读


    上一篇：颜色传感器TCS230及颜色识别电路（转）

    下一篇：MQTT简介