注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ3051][wc2013]平面图  

2015-06-20 15:35:58|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

3051: [wc2013]平面图

Time Limit: 50 Sec  Memory Limit: 512 MB
Submit: 220  Solved: 104
[Submit][Status][Discuss]

Description

Input

Output

Sample Input

Sample Input

Sample Output

2 3 -1

HINT


Solution

脑部了半天的写法
听说手写splay被卡了好桑心。。。然而set却能过。。。

Code

/**************************************************************
    Problem: 3051
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:1608 ms
    Memory:94764 kb
****************************************************************/
 
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<set>
int aa;char ch,B[1<<15],*S=B,*T=B;
#define getc() (S==T&&(T=(S=B)+fread(B,1,1<<15,stdin),S==T)?0:*S++)
#define GetAA() \
    while(ch=getc(),ch<'0'||ch>'9');aa=ch-'0';\
    while(ch=getc(),ch>='0'&&ch<='9')aa=aa*10+ch-'0'
int F(){GetAA();return aa;}
int Fl(){GetAA();return aa<<1|(ch=='.'?getc(),1:0);}
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
#define cmax(a,b) (a<b?a=b:1)
typedef double ld;
typedef long long ll;
#define N 300010
int n,m,qtot,et=1,la[N],id[N],cnt,vis[N],inf;ll sum[N];
struct E{int to,v,nxt,pre;}e[N];
void adde(int x,int y,int v){
    e[++et]=(E){y,v,la[x]},la[x]=et;
    e[++et]=(E){x,v,la[y]},la[y]=et;
}
struct P{int x,y;}p[N];
#define PP const P&
bool operator<(PP a,PP b){return a.x<b.x||a.x==b.x&&a.y<b.y;}
bool operator==(PP a,PP b){return a.x==b.x&&a.y==b.y;}
P operator-(PP a,PP b){return (P){a.x-b.x,a.y-b.y};}
ll operator*(PP a,PP b){return 1LL*a.x*b.y-1LL*a.y*b.x;}
struct D{P to;int n;};
bool operator<(const D&a,const D&b){return atan2(a.to.y,a.to.x)<atan2(b.to.y,b.to.x);}
struct Q{P p;int n;}a[N];
bool operator<(const Q&a,const Q&b){return a.p<b.p||a.p==b.p&&a.n<b.n;}
struct Graph{
    int et,la[N],q[N],l,r,fa[N][20],mx[N][20],vis[N],dep[N],ufs[N],tot;
    struct E{int to,v,nxt;}e[N<<1];
    struct H{
        int x,y,v;
        bool operator<(const H&b)const{return v<b.v;}
    }d[N];
    int gf(int x){return ufs[x]==x?x:ufs[x]=gf(ufs[x]);}
    void adde(int x,int y,int v){
        e[++et]=(E){y,v,la[x]},la[x]=et;
        e[++et]=(E){x,v,la[y]},la[y]=et;
    }
    void add(int x,int y,int v){d[++tot]=(H){x,y,v};}
    void bfs(){
        for(q[l=r=0]=inf==1?2:1,vis[inf==1?2:1]=1;l<=r;l++)
        for(int i=la[q[l]];i;i=e[i].nxt)
        if(!vis[e[i].to]){
            vis[q[++r]=e[i].to]=1;mx[e[i].to][0]=e[i].v;
            dep[e[i].to]=dep[fa[e[i].to][0]=q[l]]+1;
            for(int j=0;fa[e[i].to][j];j++)
            fa[e[i].to][j+1]=fa[fa[e[i].to][j]][j],
            mx[e[i].to][j+1]=max(mx[e[i].to][j],mx[fa[e[i].to][j]][j]);
        }
    }
    int query(int x,int y){
        int k,i,ans=0;
        if(x==inf||y==inf)return -1;
        if(dep[x]<dep[y])k=x,x=y,y=k;
        for(i=0,k=dep[x]-dep[y];k;k>>=1,i++)if(k&1)cmax(ans,mx[x][i]),x=fa[x][i];
        if(x==y)return ans;
        for(i=0;fa[x][i]!=fa[y][i];i++);
        for(i--;~i;i--)if(fa[x][i]!=fa[y][i])
        cmax(ans,mx[x][i]),x=fa[x][i],
        cmax(ans,mx[y][i]),y=fa[y][i];
        cmax(ans,mx[x][0]),cmax(ans,mx[y][0]);return ans;
    }
    void work1(){
        for(int i=1;i<=cnt;i++)ufs[i]=i;
        std::sort(d+1,d+1+tot);et=1;
        for(int i=1,x,y;i<=tot;i++)
        if((x=gf(d[i].x))!=(y=gf(d[i].y)))
        ufs[x]=y,adde(d[i].x,d[i].y,d[i].v);
        bfs();
    }
    void work2(){
        for(int i=1;i<=qtot;i++)printf("%d\n",query(id[i+n],id[i+n+qtot]));
    }
}G;
void sort_edge(int x){
    int tot=0;static D d[N];
    for(int i=la[x];i;i=e[i].nxt)d[++tot]=(D){p[e[i].to]-p[x],i};
    std::sort(d+1,d+1+tot);
    for(int i=2;i<=tot;i++)e[d[i].n].pre=d[i-1].n;
    e[d[1].n].pre=d[tot].n;
}
void get_area(int col,int i){
    int o=i;P x=p[e[i^1].to];
    for(vis[i]=col;(i=e[i^1].pre)!=o;vis[i]=col)
    sum[col]+=(p[e[i^1].to]-x)*(p[e[i].to]-x);
    if(sum[col]<0)sum[col]=-sum[col];
}
void work1(){
    for(int i=1;i<=n;i++)sort_edge(i);
    for(int i=2;i<=et;i++)if(!vis[i])get_area(++cnt,i);
    for(int i=1;i<=cnt;i++)if(sum[i]>sum[inf])inf=i;
    for(int i=2;i<=et;i++)if(vis[i]!=inf&&vis[i^1]!=inf&&vis[i^1]<vis[i])G.add(vis[i],vis[i^1],e[i].v);
}
ld nowx;
struct T{
    int tot;
    struct Node{
        ld k,b,x0;int col;
        bool operator<(const Node&a)const{return k*(nowx+0.001)+b<a.k*(nowx+0.001)+a.b||k*(nowx+0.001)+b==a.k*(nowx+0.001)+a.b&&x0<a.x0;}
    }tr[N];
    std::set<Node>s;
    std::set<Node>::iterator it[N];
    void init(){
        for(int i=2;i<=et;i+=2){
            tr[i>>1].k=1.0*(p[e[i].to].y-p[e[i^1].to].y)/(p[e[i].to].x-p[e[i^1].to].x);
            tr[i>>1].b=p[e[i].to].y-tr[i>>1].k*p[e[i].to].x;
            tr[i>>1].x0=min(p[e[i].to].x,p[e[i^1].to].x);
            if(p[e[i].to].x>p[e[i^1].to].x)tr[i>>1].col=vis[i];else tr[i>>1].col=vis[i^1];
        }
        tr[0].col=inf;tr[0].b=-1;
        tr[tot=(et>>1)+1].k=0,tr[tot].b=1<<30,tr[tot].col=inf;nowx=0;
        it[0]=s.insert(tr[0]).first;
        it[tot]=s.insert(tr[tot]).first;tot++;
    }
    void ins(int x,int k){nowx=x;it[k]=s.insert(tr[k]).first;}
    void del(int k){s.erase(it[k]);}
    void query(int o,int x,int y){
        nowx=x,tr[tot].k=0,tr[tot].b=y;
        id[o]=(*--s.lower_bound(tr[tot])).col;
    }
}tree;
void work2(){
    qtot=F();int tot=n;
    for(int i=1;i<=qtot;i++)id[i]=inf,
    a[++tot].p=(P){Fl(),Fl()},a[tot].n=i+n,
    a[++tot].p=(P){Fl(),Fl()},a[tot].n=i+n+qtot;
    std::sort(a+1,a+1+n+qtot*2);tree.init();
    for(int i=1;i<=tot;i++)
    if(a[i].n<=n){
        for(int j=la[a[i].n];j;j=e[j].nxt)
        if(p[a[i].n].x!=p[e[j].to].x)
        if(p[a[i].n].x>p[e[j].to].x)tree.del(j>>1);
        else tree.ins(p[a[i].n].x,j>>1);
    }
    else tree.query(a[i].n,a[i].p.x,a[i].p.y);
}
int main(){
    n=F(),m=F();G.et=1;
    for(int i=1;i<=n;i++)a[i].p=p[i]=(P){Fl(),Fl()},a[i].n=i;
    for(int i=1,x,y,v;i<=m;i++)x=F(),y=F(),v=F(),adde(x,y,v);
    work1();G.work1();
    work2();G.work2();
}
  评论这张
 
阅读(46)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018