码农题

平面图点定位：

1.平面图转对偶图：

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的。

 

大致解释

code：并不能过UOJhack数据

#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;template
        
         il 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);}template
         
          il void output(T x){
    if(x/10)output(x/10);putchar(x%10+'0');}template
          
           il void ot(T x){
    if(x<0) putchar('-'),x=-x;output(x);putchar(' ');}template
           
            il 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.z
            
             exi;//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.x
             
              to[N];int nxt[2*N];int nc;//newcurint 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];vector
                  
                   del[3*N];vector
                   
                    ins[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