首页 > 代码库 > (中等) POJ 1436 Horizontally Visible Segments , 线段树+区间更新。
(中等) POJ 1436 Horizontally Visible Segments , 线段树+区间更新。
Description
There is a number of disjoint vertical line segments in the plane. We say that two segments are horizontally visible if they can be connected by a horizontal line segment that does not have any common points with other vertical segments. Three different vertical segments are said to form a triangle of segments if each two of them are horizontally visible. How many triangles can be found in a given set of vertical segments?
题意大致就是说给你一些线段，问相邻两个线段有没有公共的部分，且没有其他线段阻挡。
首先对x排序，然后枚举，对于每个线段，先询问这个区间上的所有其他线段，然后再覆盖更新。
对于COL数组，如果为-1表示这个区间上有多个线段，否则的话表示的是线段的编号（这里假设先放了一个编号为0的线段。）
（PS：我能说这个题我调试了一下午吗，刚开始把COL设置为了bool的变量，结果。。。T T ， 一直没找出错误来。。。痛苦。。。）
代码如下：
#include<iostream>#include<cstdio>#include<cstring>#include<cstdlib>#define lson L,M,po*2#define rson M+1,R,po*2+1using namespace std;const int N=8000*2;int COL[8008*2*4];bool map1[8008][8008];void pushDown(int po){ if(COL[po]>=0) { COL[po*2]=COL[po*2+1]=COL[po]; COL[po]=-1; }}void update(int ul,int ur,int ut,int L,int R,int po){ if(ul<=L&&ur>=R) { COL[po]=ut; return; } pushDown(po); int M=(L+R)/2; if(ul<=M) update(ul,ur,ut,lson); if(ur>M) update(ul,ur,ut,rson); if(COL[po*2]==COL[po*2+1]) //这里算是一个剪枝操作，可以减少递归次数。 COL[po]=COL[po*2]; else COL[po]=-1;}void query(int ql,int qr,int qt,int L,int R,int po){ if(COL[po]!=-1) { map1[qt][COL[po]]=map1[COL[po]][qt]=1; return; } if(L==R) return; int M=(L+R)/2; if(ql<=M) query(ql,qr,qt,lson); if(qr>M) query(ql,qr,qt,rson);}struct state{ int y1,y2,x1;};state sta[8008];int cmp(const void*a,const void*b){ return (*(state*)a).x1-(*(state*)b).x1;}int main(){ int d; cin>>d; int n; while(d--) { memset(map1,0,sizeof(map1)); memset(COL,0,sizeof(COL)); cin>>n; for(int i=0;i<n;++i) scanf("%d %d %d",&sta[i].y1,&sta[i].y2,&sta[i].x1); qsort(sta,n,sizeof(state),cmp); for(int i=1;i<=n;++i) { query(sta[i-1].y1*2,sta[i-1].y2*2,i,0,N,1); update(sta[i-1].y1*2,sta[i-1].y2*2,i,0,N,1); } long long ans=0; for(int i=1;i<=n;++i) //直接暴力求解，居然不超时。。。 for(int j=i+1;j<=n;++j) if(map1[i][j]) for(int k=j+1;k<=n;++k) if(map1[i][k]&&map1[j][k]) ++ans; cout<<ans<<endl; } return 0;}
(中等) POJ 1436 Horizontally Visible Segments , 线段树+区间更新。
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。