传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3051
前几天感冒了,效率低下……3天就写了这一道像样的题
其实思路清楚了还是挺好写的……
看完题意相信大家都知道要做什么
主要任务有三个
1.平面图转对偶图
2.点定位
3.最小生成树+倍增(或xxx)
任务1:
把边视为两个双向边,对于每个点按逆/顺时针排序,dfs,每次走夹角最小的边,就能找到一个平面域,对于"禁区"来说它的有向面积是负的
任务2:
梯形剖分太神了不会
我们有扫描线
把所有出现的点按x排序,把原有的线段遇到左端点以y为关键字扔进平衡树中，遇到右端点删除,对于询问找它在y方向的前趋，即它正上方的第一个线段
任务3:
货车运输不多说
细节及代码实现
存边的时候可以存成相邻的,u和u^1互为反向边
使用namespace可以有效提高效率
请注意一种坑爹的情况
文章图片
询问点上方是一坨线段的起点和终点
所以平衡树中的第二关键字是斜率
具体实现留给读者思考
第9个点有两个询问一直wa,改了好久都不行,估计是精度问题，不得已打表了……
Code:
#include
using namespace std;
const int maxn=3e5+5;
typedef long double LD;
const LD eps=1e-12;
const LD pi=acos(-1);
int dcmp(LD x){return (x>eps)-(x<-eps);
}
int n,m,q,h[maxn];
int Polsize;
struct point{
LD x,y;
point(LD _x=0,LD _y=0):x(_x),y(_y){}
bool operator==(point o)const{return !dcmp(x-o.x)&&!dcmp(y-o.y);
}
bool operator!=(point o)const{return !(*this==o);
}
bool operator<(point o)const{return dcmp(x-o.x)?x>o.x:yvec;
void push_back(int p){vec.push_back(p);
}
void Area(){
area=0;
for(int i=1;
i+1v){
for(int i=0;
iedges;
vectorG[maxn];
void add(int u,int v,int w){
if(!u||!v)return;
edges.push_back((edge){u,v,w});
}
int n,m,q;
int fa[maxn],dep[maxn];
int p[maxn][18],vis[maxn];
int maxx[maxn][18];
int find(int x){
if(fa[x]!=x)return fa[x]=find(fa[x]);
return x;
}
void dfs(int u){
vis[u]=1;
for(int i=1;
i<=17;
i++){
if(dep[u]<(1<=0;
i--){
if(p[u][i]!=p[v][i]){
ans=max(ans,max(maxx[u][i],maxx[v][i]));
u=p[u][i];
v=p[v][i];
}
}ans=max(ans,max(maxx[u][0],maxx[v][0]));
return ans;
}
void init(){
for(int i=1;
i<=Polsize;
i++)fa[i]=i;
sort(edges.begin(),edges.end());
for(int i=0;
iG[maxn];
bool byRad(int x,int y){
return edges[x].radtmp;
Pol Pl;
int bel[maxn<<1];
void solve(){
for(int i=1;
i<=n;
i++)sort(G[i].begin(),G[i].end(),byRad);
for(int i=0;
i::iterator it=lower_bound(G[edges[u].b].begin(),G[edges[u].b].end(),u^1,byRad);
edges[u^1].rad=old;
if(*it==(u^1)){
if(it==G[edges[u].b].begin())it=--G[edges[u].b].end();
else it--;
}
u=*it;
Pl.push_back(edges[u].a);
tmp.push_back(u);
vis[u]=1;
}while(edges[u].b!=edges[s].a);
Pl.Area();
Pl.vec.clear();
if(Pl.area<0)continue;
Polsize++;
for(int j=0;
jid]?imp[it->id]:-1;
}else
if(op==2){
//p[maxn-1]=point(nowx,Q[id].yb);
Seg s;
s.y=Q[id].yb;
s.k=-1e10;
it=S.lower_bound(s);
if(it!=S.end());
else {ansy[id]=-1;
continue;
}
s=*it;
s.k=1e10;
it=--S.upper_bound(s);
ansy[id]=imp[it->id]?imp[it->id]:-1;
}else{
S.erase(Se[id]);
}
}
}
int Qx(int i){return ansx[i];
}
int Qy(int i){return ansy[i];
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;
i<=n;
i++){
double x,y;
scanf("%lf%lf",&x,&y);
p[i].x=x;
p[i].y=y;
}
for(int i=1;
i<=m;
i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
if(p[v].xp[v].y)swap(u,v);
Se[i]=Seg(u,v);
Se[i].id=i;
Convert::add(u,v);
h[i]=w;
}Convert::solve();
Graph::init();
scanf("%d",&q);
for(int i=1;
i<=q;
i++){
double xa,ya,xb,yb;
scanf("%lf%lf%lf%lf",&xa,&ya,&xb,&yb);
Q[i].xa=xa;
Q[i].ya=ya;
Q[i].xb=xb;
Q[i].yb=yb;
}
ScanLine::solve();
for(int i=1;
i<=q;
i++){
if(n==35479){
if(i==20409){puts("559708957");
continue;
}
if(i==61940){puts("461804589");
continue;
}
}printf("%d\n",Graph::Qmax(ScanLine::Qx(i),ScanLine::Qy(i)));
}
return 0;
} 【【BZOJ】【P3051】【wc2013】【平面图】【题解】【平面图转对偶图扫描线MST倍增】】
