首页 > 代码库 > POJ 1436 Horizontally Visible Segments
POJ 1436 Horizontally Visible Segments
题意：
有一些平行于y轴的线段 ，两条线段称为互相可见当且仅当存在一条水平线段连接这两条 与其他线段没交点。 最后问有多少组 3条线段，他们两两是可见的。
思路：
线段树，找出两两可见的那些组合，最后暴力判断。
#include<cstring>#include<cstdio>#include<algorithm>#include<cmath>#include<iostream>#include<vector>#define debug(x) printf(#x"= %d \n",x);#define N 20000using namespace std;int id[N*4];vector<int>e[N];void build(int l,int r,int i){ id[i]=0; if(l!=r) { int mid=(l+r)>>1; build(l,mid,i<<1); build(mid+1,r,i<<1|1); }}void pushdown(int i){ if(id[i]!=-1) { id[i<<1]=id[i<<1|1]=id[i]; id[i]=-1; }}void update(int l,int r,int pl,int pr,int va,int i){ if(l>=pl&&r<=pr) { if(id[i]!=-1) { e[id[i]].push_back(va); id[i]=va; return; } id[i]=va; } if(id[i]!=va) pushdown(i); int mid=(l+r)>>1; if(pl<=mid)update(l,mid,pl,pr,va,i<<1); if(pr>mid)update(mid+1,r,pl,pr,va,i<<1|1);}struct node{ int y1,y2,x;}s[16000];bool cmp(node a,node b){ return a.x<b.x;}int cas[N];int main() { int tt,n,ri=0; memset(cas,0,sizeof(cas)); scanf("%d",&tt); while(tt--) { int maxn=17000; build(1,maxn,1); scanf("%d",&n); for(int i=1;i<=n;++i) { scanf("%d%d%d",&s[i].y1,&s[i].y2,&s[i].x); s[i].y1++; s[i].y2++; s[i].y1=s[i].y1*2-1; s[i].y2=s[i].y2*2-1; } sort(s+1,s+n+1,cmp); for(int i=0;i<=n;++i)e[i].clear(); for(int i=1;i<=n;++i) { int l,r; l=s[i].y1; r=s[i].y2; update(1,maxn,l,r,i,1); } for(int i=1;i<=n;++i) { sort(e[i].begin(),e[i].end()); e[i].erase(unique(e[i].begin(),e[i].end()),e[i].end());//去重 } int ans=0; for(int i=1;i<=n;++i) { ri++; for(int j=0;j<e[i].size();++j) cas[e[i][j]]=ri; for(int j=0;j<e[i].size();++j) { int now=e[i][j]; for(int k=0;k<e[now].size();++k) { if(cas[e[now][k]]==ri) { // printf("%d %d %d\n",i,now,e[now][k]); ans++; } } } } printf("%d\n",ans); } return 0;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。