程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> poj1436 Horizontally Visible Segments

poj1436 Horizontally Visible Segments

編輯：C++入門知識

poj1436 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?

Task

Write a program which for each data set:

reads the description of a set of vertical segments,

computes the number of triangles in this set,

writes the result.

Input

The first line of the input contains exactly one positive integer d equal to the number of data sets, 1 <= d <= 20. The data sets follow.

The first line of each data set contains exactly one integer n, 1 <= n <= 8 000, equal to the number of vertical line segments.

Each of the following n lines consists of exactly 3 nonnegative integers separated by single spaces:

yi', yi'', xi - y-coordinate of the beginning of a segment, y-coordinate of its end and its x-coordinate, respectively. The coordinates satisfy 0 <= yi' < yi'' <= 8 000, 0 <= xi <= 8 000. The segments are disjoint.

Output

The output should consist of exactly d lines, one line for each data set. Line i should contain exactly one integer equal to the number of triangles in the i-th data set.

Sample Input

Sample Output

題意是如果兩條線段之間能被一條平行於x軸的線段相連且這條線段和其他線段沒有交點，那麼這兩條線段可見，如果三條線段每兩條線段可見，那麼他們能組成特定三角形，那麼問三角形有多少個。這題先把所有線段儲存起來，按x大小升序排列，然後相當於依次讀入不同顏色的線段，每次操作，先判斷這條線段所在的縱坐標范圍內顏色種類，這些顏色種類對應的線段和當前這條線段是可見的，接著把這條線段插入區間，更新總區間的顏色。這裡有一點要注意，為了避免單位元線段被“忽略”，把所有的縱坐標都乘2.如3 0 4 1 0 2 2 3 4 2這組數據不乘2的話2-3會被忽略。剛開始所有顏色都為0，如果線段是純色，那麼為大於0的數，若為-1，則是雜色，要在子區間找。

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;

struct node{
	int l,r,cnt;
}b[8*8005];

struct edge{
	int y2,y3,x;
}s[8005];
bool cmp(edge a,edge b){
	return a.xmid)update(l,r,value,i*2+1);
	else {
		update(l,mid,value,i*2);
		update(mid+1,r,value,i*2+1);
	}
}

void question(int l,int r,int id,int i)
{
	int mid;
	if(b[i].cnt>0){
		mark[b[i].cnt][id]=true;return;
	}
	if(b[i].cnt==0 || (b[i].l==b[i].r))return;
	mid=(b[i].l+b[i].r)/2;
	if(r<=mid)question(l,r,id,i*2);
	else if(l>mid)question(l,r,id,i*2+1);
	else {
		question(l,mid,id,i*2);
		question(mid+1,r,id,i*2+1);
	}
}

int main()
{
	int n,m,i,j,T,x,y2,y3,ans;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		for(i=1;i<=n;i++){
			scanf("%d%d%d",&y2,&y3,&x);
			s[i].y2=2*y2;s[i].y3=2*y3;s[i].x=x;
		}
		sort(s+1,s+n+1,cmp);
		memset(mark,false,sizeof(mark));
		build(0,16000,1);
		for(i=1;i<=n;i++){
			question(s[i].y2,s[i].y3,i,1);
			update(s[i].y2,s[i].y3,i,1);
		}
		
		ans=0;
		for(i=1;i<=n;i++){
			for(j=i+1;j<=n;j++){
				if(mark[i][j])
				{
					for(k=j+1;k<=n;k++){
					  if(mark[j][k] && mark[i][k]){
						ans++;
						//printf("%d %d %d\n",i,j,k);
					  }
				    }
				}
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}