当前位置: 代码迷 >> 综合 >> POJ 1436 Horizontally Visible Segments(线段树)
  详细解决方案

POJ 1436 Horizontally Visible Segments(线段树)

热度:62   发布时间:2023-12-17 03:33:33.0

题意:

给你一堆平行于y轴的线,如果两条线之间能够有一条平行于x轴的线直接相连,就说这两条线是可见的,现在给你n条线,问有多少组线,每组要求三条且两两可见

思路:

首先离散所有y轴的点,然后按照x轴排序,这样我们不断地更新线段树,每次先看看能看到那些线段,再把当前这条线更新进去,就能知道某条线与哪些其他线两两可见,最后暴力地看有多少组即可(虽然最差的时候我们我们每次查询都要查到最下面,但是因为时间限制比较宽且线段最多也就维护16000个点,所以不会T)

错误及反思:

没想到最后居然可以直接暴力地求有多少组。。。。

代码:

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int N =8010;
int segtree[(2*N)*4];
struct line
{int x,y1,y2,id;
}L[N];
bool vis[N][N];
bool cmp(line w,line y)
{return w.x<y.x;
}
void inti()
{memset(segtree,0,sizeof(segtree));memset(vis,false,sizeof(vis));
}
void pushdown(int rt)
{if(segtree[rt]!=-1){segtree[rt<<1]=segtree[rt];segtree[rt<<1|1]=segtree[rt];}
}
void pushup(int rt)
{if(segtree[rt<<1]==segtree[rt<<1|1]) segtree[rt]=segtree[rt<<1];else segtree[rt]=-1;
}
void query(int L,int R,int num,int l,int r,int rt)
{if(L<=l&&R>=r){if(segtree[rt]==0)return ;if(segtree[rt]!=-1){vis[num-1][segtree[rt]-1]=true;vis[segtree[rt]-1][num-1]=true;return ;}}pushdown(rt);int m=(l+r)/2;if(L<=m) query(L,R,num,lson);if(m<R) query(L,R,num,rson);pushup(rt);return ;
}
void update(int L,int R,int num,int l,int r,int rt)
{if(L<=l&&R>=r){segtree[rt]=num;return ;}pushdown(rt);int m=(l+r)/2;if(L<=m) update(L,R,num,lson);if(m<R) update(L,R,num,rson);pushup(rt);return ;
}
int main()
{int T;scanf("%d",&T);while(T--){int n;inti();scanf("%d",&n);for(int i=0;i<n;i++){scanf("%d%d%d",&L[i].y1,&L[i].y2,&L[i].x);L[i].id=i+1;}sort(L,L+n,cmp);for(int i=0;i<n;i++){query(L[i].y1*2,L[i].y2*2,L[i].id,0,16001,1);update(L[i].y1*2,L[i].y2*2,L[i].id,0,16001,1);}int ans=0;for(int i=0;i<8001;i++){for(int j=i+1;j<8001;j++){if(vis[i][j]){for(int k=j+1;k<8001;k++){if(vis[i][k]&&vis[j][k])ans++;}}}}printf("%d\n",ans);}
}
  相关解决方案