題目大意：

在一個平面內，有一些豎直的線段，若兩條豎直線段之間可以連一條水平線，這條水平線不與其他豎直線段相交，稱這兩條豎直線段為“相互可見”的。若存在三條豎直線段，兩兩“相互可見”，則構成“線段三角形”。給出一些豎直的線段，問一共有多少“線段三角形”。

?

首先處理端點問題：想象一下若同一x位置有兩條線段，y坐標為1~2和3~4。其實中間的空當2~3之間是可以引水平線段的，而這里我們都用整數處理，那條水平線段就被忽略了，可能會導致有一些水平相互可見的線段在計算中被忽略了，這里我們擴大y坐標之間的空間，這時我們就可以多出一個整數來便于我們的整數處理，這樣就可以簡單地處理端點問題,并且它對于所有情況都有很好的效果.自己畫個圖就明白了。

?

線段處理：首先對線段以X大小進行排序；再進行詢問，詢問時是以當前的線段與先前的線段是不是“相互可見”的；再進行更新。

這里我們用到了覆蓋的原則。如果不明白先做做這個題吧。http://poj.org/problem?id=2777

?

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
class Node
{
public:
int l ,r ,c;
};
class segment
{
public:
int y1,y2,x;
};
Node tree[40024];
int v[10024];
segment seg[10024];
vector<int>see[10024];
class Tree
{
public:
void Maketree( int l, int r ,int cnt );
void Update( int l, int r ,int cnt, int id );
void Query( int l ,int r, int cnt, int id );
};
void Tree::Maketree( int l ,int r, int cnt )
{
tree[cnt].l = l;
tree[cnt].r = r;
tree[cnt].c = -1;//-1表示該區間有個線段；
if( l == r ) return ;
int mid = ( l + r )>>1;
Maketree( l , mid , cnt*2 );
Maketree( mid + 1 ,r ,cnt*2+1 );
}
void Tree::Update( int l ,int r, int cnt , int id )
{
if( l <= tree[cnt].l&& r >= tree[cnt].r )//符合要求的區間被覆蓋
{
tree[cnt].c = id;
return;
}
else
{
if( tree[cnt].c != -1 )//如果不為-1則表示該區間（y軸這個區間）只有一條線段那么就要復原
{
tree[cnt*2].c = tree[cnt*2+1].c = tree[cnt].c;
tree[cnt].c = -1;
}
int mid = ( tree[cnt].l + tree[cnt].r )>>1;
if( r > mid )
Update( l , r , cnt*2 +1 , id );
if( l <= mid )
Update( l , r , cnt*2 , id );
if( tree[cnt*2].c == tree[cnt*2+1].c )//由下往上更新
tree[cnt].c = tree[cnt*2].c;
else tree[cnt].c = -1;
}
}
void Tree::Query(int l, int r ,int cnt , int id)
{
// if( l > tree[cnt].r || r > tree[cnt].l )
// return ;
if( tree[cnt].c != -1 )
{
if( v[tree[cnt].c] != id )
{
see[ tree[cnt].c ].push_back( id );
v[tree[cnt].c] = id;
}
return ;
}
// Query( l , r, cnt*2 + 1, id );
// Query( l , r , cnt *2 ,id );
if( tree[cnt].l == tree[cnt].r ) return;
else
{
int mid = ( tree[cnt].l + tree[cnt].r )>>1;
if( mid < l )
Query( l , r, cnt*2 + 1, id );
else
{
if( r <= mid )
Query( l , r, cnt*2 , id );
else
{
Query( l , mid , cnt *2 ,id );
Query( mid + 1 , r ,cnt*2+1 , id );
}
}
}
}
bool cmp( segment a ,segment b )
{
return a.x < b.x;
}
int main( )
{
int n,m;
while( scanf( "%d",&n )==1 )
{
while( n-- )
{
Tree e;
scanf( "%d",&m );
for( int i=0; i<m ;i++ )
{
scanf( "%d%d%d",&seg[i].y1, &seg[i].y2 ,&seg[i].x );
seg[i].y1 *= 2;
seg[i].y2 *= 2;
see[i].clear();
}
e.Maketree( 0 , 16000 , 1 );
sort( seg , seg+m ,cmp );
memset( v , -1 ,sizeof( v ) );
for( int i = 0 ; i< m ;i++ )
{
e.Query( seg[i].y1, seg[i].y2 , 1 , i );
e.Update( seg[i].y1 , seg[i]. y2 , 1 ,i );
}
int ans = 0;
for( int i= 0 ; i < m ;i++ )
{
int t = see[i].size();
for( int j= 0 ; j< t ;j++ )
{
for( int k = j+1 ;k< t ;k++ )
{
int z = see[see[i][j]].size();
for( int l = 0 ; l < z ; l++ )
{
if( see[i][k] == see[see[i][j]][l] )
{
ans++;
break;
}
}
}
}
}
printf( "%d\n",ans );
}
}
return 0;
}

轉載于:https://www.cnblogs.com/bo-tao/archive/2012/02/27/2370276.html

總結

以上是生活随笔為你收集整理的poj 1436 Horizontally Visible Segments的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。