[WC2013]平面图-平面图点定位-学习笔记
i207M
2019-05-03 21:57:57
<见猫锟五一集训>
简单的说，就是平面图转对偶图，然后扫描线，维护线段按y排序的顺序。
~~好像跑得非常快！？~~
~~UOJ上过不了Hack#8，疑似被卡精度~~
```cpp
#pragma region
#include <bits/stdc++.h>
using namespace std;
#define ri register int
#define il inline
#define LL long long
#define uint unsigned int
#define ull unsigned long long
#define solid const auto &
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define pll pair<LL,LL>
#define fi first
#define se second
#define gm int mid((l+r)/2)
#define space putchar(' ')
#define enter putchar('\n')
#define rd() ({ri t;in(t);t;})
#define Size(x) ((int)x.size())
#define mem(x,y) memset(x,y,sizeof(x))
template<class T>il void in(T &x)
{
x=0; char c=getchar(); bool f=0;
while(!isdigit(c)) f|=(c=='-'),c=getchar();
while(isdigit(c)) x=x*10+(c^'0'),c=getchar();
f?x=-x:0;
}
template<class T>il void out(T x,const char c='\n')
{
static short st[30]; short m=0;
if(x<0) putchar('-'),x=-x;
do st[++m]=x%10,x/=10; while(x);
while(m) putchar(st[m--]|'0');
putchar(c);
}
template<class T>il void err(const T &x,const char c='\n') {cerr<<x<<c;}
template<class T,class ...Args>il void in(T &x,Args &...args) {in(x); in(args...);}
template<class T,class ...Args>il void out(const T &x,const Args &...args) {out(x,' '); out(args...);}
template<class T,class ...Args>il void err(const T &x,const Args &...args) {err(x,' '); err(args...);}
template<class T>il void prt(T a[],int n) {for(ri i=0; i<n; ++i) out(a[i],i==n-1?'\n':' ');}
template<class T>il void clr(T a[],int n) {memset(a,0,sizeof(T)*n);}
template<class T>il void clr(T *a,T *b) {memset(a,0,sizeof(T)*(b-a));}
template<class T>il bool ckmax(T &a,const T &b) {return a<b?a=b,1:0;}
template<class T>il bool ckmin(T &a,const T &b) {return a>b?a=b,1:0;}
namespace MOD_CALC
{
const int md=1e9+7;
il int add(const int a,const int b) {return a+b>=md?a+b-md:a+b;}
il int sub(const int a,const int b) {return a-b<0?a-b+md:a-b;}
il int mul(const int a,const int b) {return (LL)a*b%md;}
il void inc(int &a,const int b) {(a+=b)>=md?a-=md:0;}
il void dec(int &a,const int b) {(a-=b)<0?a+=md:0;}
il int qpow(int a,int b) {int r=1; for(; b; b>>=1,a=mul(a,a)) if(b&1) r=mul(r,a); return r;}
il int qpow(int a,int b,const int p) {int r=1; for(; b; b>>=1,a=(LL)a*a%p) if(b&1) r=(LL)r*a%p; return r;}
il int mdinv(const int a) {return qpow(a,md-2);}
template<class ...Args>il int add(const int a,const int b,const Args &...args) {return add(add(a,b),args...);}
template<class ...Args>il int mul(const int a,const int b,const Args &...args) {return mul(mul(a,b),args...);}
} using namespace MOD_CALC;
namespace i207M
{
#pragma endregion
#define N 100005
pii wen[N]; int cq;
int ans[N];
namespace S
{
struct Edge
{
int u,v,w;
Edge() {}
Edge(const int uu,const int vv,const int ww) {u=uu,v=vv,w=ww;}
friend bool operator<(const Edge &a,const Edge &b)
{
return a.w<b.w;
}
} e[N]; int cnte;
int n;
int uf[N];
il int ufind(int x) {return x==uf[x]?x:uf[x]=ufind(uf[x]);}
vector< pii > qu[N];
void solve()
{
for(ri i=1; i<=cq; ++i)
{
if(ans[i]==-1||wen[i].fi==wen[i].se) continue;
qu[wen[i].fi].pb(mp(wen[i].se,i));
qu[wen[i].se].pb(mp(wen[i].fi,i));
}
sort(e+1,e+1+cnte);
for(ri i=1; i<=n; ++i) uf[i]=i;
for(ri i=1; i<=cnte; ++i)
{
int x=ufind(e[i].u),y=ufind(e[i].v);
if(x==y) continue;
if(Size(qu[x])>Size(qu[y])) swap(x,y);
for(solid it:qu[x])
{
if(ans[it.se]) continue;
if(ufind(it.fi)==y) ans[it.se]=e[i].w;
else qu[y].pb(it);
}
qu[x].clear();
uf[x]=y;
}
for(ri i=1; i<=cq; ++i)
if(ans[i]==-1||ufind(wen[i].fi)!=ufind(wen[i].se)) out(-1);
else out(ans[i]);
}
}
int n,m;
struct Node
{
int x,y;
Node() {}
Node(const int _x,const int _y) {x=_y,y=_y;}
friend bool operator<(const Node &a,const Node &b)
{
return a.x==b.x?a.y<b.y:a.x<b.x;
}
} pt[N];
il LL cross(const Node &a,const Node &b)
{
return (LL)a.x*b.y-(LL)a.y*b.x;
}
struct Edge
{
int v,id;
double ang;
void init(int uu,int vv,int _id)
{
v=vv,id=_id;
ang=atan2(pt[vv].y-pt[uu].y,pt[vv].x-pt[uu].x);
}
friend bool operator<(const Edge &a,const Edge &b)
{
return a.ang<b.ang;
}
} e[N*2]; int cnte=1;
int we[N];
int pos[N*2];
int visp[N],cur;
bool vise[N*2];
int eto[N*2];
bool neg[N];
LL are;
int tot;
vector<Edge>E[N];
void dfs(int x,const Edge &it)
{
if(visp[x]==cur) return;
visp[x]=cur;
are+=cross(pt[x],pt[it.v]);
vise[it.id]=1;
eto[it.id]=tot;
int k=pos[it.id^1];
if(k==0) dfs(it.v,E[it.v].back());
else dfs(it.v,E[it.v][k-1]);
}
#define eps 1e-5
double curx;
struct Line
{
int dn;
double k,b;
Line() {}
explicit Line(const int x) {b=x,k=dn=0;}
void init(int uu,int vv,int _dn)
{
dn=_dn;
k=(double)(pt[vv].y-pt[uu].y)/(pt[vv].x-pt[uu].x);
b=pt[uu].y-k*pt[uu].x;
}
friend bool operator<(const Line &a,const Line &b)
{
return a.k*curx+a.b<b.k*curx+b.b;
}
} lin[N];
pii opt[N*2]; int cnto;
void prework()
{
for(ri i=1; i<=n; ++i)
for(solid it:E[i])
{
if(vise[it.id]) continue;
are=0,++tot,++cur;
dfs(i,it);
neg[tot]=(are<0);
}
S::n=tot;
for(ri i=2; i<=cnte; i+=2)
{
if(!neg[eto[i]]&&!neg[eto[i^1]])
S::e[++S::cnte]=S::Edge(eto[i],eto[i^1],we[i>>1]);
int uu=e[i^1].v,vv=e[i].v;
if(pt[uu].x==pt[vv].x) continue;
lin[i>>1].init(uu,vv,pt[uu].x<pt[vv].x?eto[i^1]:eto[i]);
opt[++cnto]=mp(min(pt[uu].x,pt[vv].x),i>>1);
opt[++cnto]=mp(max(pt[uu].x,pt[vv].x),-(i>>1));
}
}
pair<Node,int> qu[N*2]; int cntq;
multiset<Line> st;
void solve()
{
sort(qu+1,qu+1+cntq);
sort(opt+1,opt+1+cnto);
int p=1;
for(ri i=1; i<=cntq; ++i)
{
while(p<=cnto&&opt[p].fi<=qu[i].fi.x)
{
solid it=opt[p++];
if(it.se>0)
{
curx=it.fi+eps;
st.insert(lin[it.se]);
}
else
{
curx=it.fi-eps;
st.erase(lin[-it.se]);
}
}
curx=qu[i].fi.x+eps;
auto it=st.upper_bound(Line(qu[i].fi.y));
if(it==st.end()||neg[it->dn]) ans[abs(qu[i].se)]=-1;
else if(qu[i].se>0) wen[qu[i].se].fi=it->dn;
else wen[-qu[i].se].se=it->dn;
}
}
signed main()
{
#ifdef M207
freopen("in.in","r",stdin);
// freopen("ot.out","w",stdout);
#endif
in(n,m);
for(ri i=1; i<=n; ++i) in(pt[i].x,pt[i].y),pt[i].x<<=1,pt[i].y<<=1;
for(ri i=1,a,b; i<=m; ++i)
{
in(a,b,we[i]);
++cnte,e[cnte].init(a,b,cnte);
E[a].pb(e[cnte]);
++cnte,e[cnte].init(b,a,cnte);
E[b].pb(e[cnte]);
}
for(ri i=1; i<=n; ++i)
{
sort(E[i].begin(),E[i].end());
for(ri j=0; j<Size(E[i]); ++j) pos[E[i][j].id]=j;
}
in(cq);
for(ri i=1; i<=cq; ++i)
{
static double a,b;
scanf("%lf%lf",&a,&b);
qu[++cntq].fi.x=a*2,qu[cntq].fi.y=b*2;
qu[cntq].se=i;
scanf("%lf%lf",&a,&b);
qu[++cntq].fi.x=a*2,qu[cntq].fi.y=b*2;
qu[cntq].se=-i;
}
prework();
solve();
S::solve();
return 0;
}
#pragma region
}
signed main()
{
i207M::main();
return 0;
}
#pragma endregion
```