http://poj.org/problem?id=1436
题意:
有N根竖直的杆子,每个杆子都用一个长度,两根杆子可以想见意味着两个杆子在水平
方向上存在一条直线,使得该直线连接两个杆子,并且该水平直线和其他的杆子都没有
交点,问一共有多少对三根杆子的组合使得杆子两两可见。
思路:
首先我们可以依次枚举一根杆子作为三根中的某一根,然后再在与这根可见的杆子中找
两根互相可见的杆子。这里的主要问题就变成了如何判断两根杆子是否可见,暴力判断
肯定是不行的,所以我们就想到将两根杆子一起投影到Y轴上,然后判断两根杆子的投影
是否有交点来判断是否可见,这样就很自然地会想到线段树。但是还有一个问题,线段
树的覆盖是对整点的覆盖,并不是完全意义上的对线段的覆盖,因此我们需要将所有的
整点都*2来处理。
总结思路如下:用线段树覆盖,找到每根杆子的左边与之相见的杆子,然后依次枚举一根
最后的杆子,找前面的两个杆子,并判断它们是否可见 ,从而找出所有的解。
代码:
#include<stdio.h> #include<string.h> #include<algorithm> #include<vector> #define L(a) ( (a)<<1 ) #define R(a) ( (a)<<1|1 ) using namespace std; const int MAXN = 8010 ; int N ; struct Node{ int s , e , x ; bool operator < (const Node& n1 ) const{ return x < n1.x ; } }p[MAXN] ; const int NN = 80010*2 ; int cc[NN<<2] , ss[NN<<2] ; int hash[MAXN] ; vector<int> g[MAXN]; void init(){ int a, b, c ; for(int i=1;i<=N;i++){ scanf("%d %d %d",&a,&b,&c); p[i].x = c ; p[i].s = a << 1 ; p[i].e = b << 1 ; } sort(p+1 , p+1+N); } void down(int l, int r , int idx){ if( ss[idx] > 0 ){ ss[ L(idx) ] = ss[ R(idx) ] = ss[idx] ; cc[ L(idx) ] = cc[ R(idx) ] = ss[idx] ; ss[idx] = 0; } } void up(int l ,int r , int idx){ if( cc[ L(idx) ] == cc[ R(idx) ]) cc[idx] = cc[ L(idx) ] ; else cc[idx] = -1 ; } void query(int l ,int r, int idx, int a, int b , int x){ if( cc[idx] != -1 ){ if( hash[ cc[idx] ] != x ){ g[x].push_back( cc[idx] ); hash[ cc[idx] ] = x ; } return ; } if(l == r) return ; down( l ,r , idx); int mid = (l + r ) >> 1 ; if( b<=mid ) query(l , mid, L(idx) , a , b , x) ; else if( mid<a ) query(mid+1, r , R(idx) ,a , b, x); else{ query(l , mid, L(idx) , a , mid , x) ; query(mid+1, r ,R(idx) , mid+1, b , x) ; } } void update(int l ,int r, int idx ,int a, int b , int x){ if( a<=l && r<=b){ cc[idx] = ss[idx] = x ; return ; } down(l ,r ,idx); int mid = (l + r) >> 1 ; if( b<=mid ) update(l ,mid ,L(idx) ,a, b , x) ; else if( mid<a ) update(mid+1, r, R(idx) ,a, b, x) ; else{ update(l , mid, L(idx) ,a ,mid, x) ; update(mid+1, r, R(idx) , mid+1, b , x ) ; } up( l ,r , idx); } void solve(){ memset( cc , -1, sizeof(cc) ); memset( ss , 0 , sizeof(ss) ); memset( hash , -1 , sizeof(hash) ); for(int i=1;i<=N;i++){ g[i].clear() ; query(1 , NN, 1 , p[i].s , p[i].e , i ) ; update(1, NN , 1 , p[i].s , p[i].e , i ) ; } int ans = 0 ; for(int i=1;i<=N;i++){ int sz = g[i].size() ; for(int j=0;j<sz;j++){ for(int k=j+1;k<sz;k++){ int a = g[i][j] ; int b = g[i][k] ; if(a < b) { int c = a ; a = b; b = c ; } for(int ii=0;ii<g[a].size();ii++) if(b == g[a][ii]) ans++ ; } } } printf("%d\n",ans); } int main(){ int t , tt ; scanf("%d",&tt); for(t=0;t<tt;t++){ scanf("%d",&N); init() ; solve() ; } return 0 ; }