首页 > 代码库 > POJ - 1436 Horizontally Visible Segments

POJ - 1436 Horizontally Visible Segments

2024-07-15 14:30:22   216人阅读

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

1
5
0 4 4
0 3 1
3 4 2
0 2 2
0 2 3

Sample Output

1

题意：平面上有几个垂直的线，现在有如果两个垂直的线之间有一条连线并不会经过其他的垂直线的话，那么我们就说这两个线是互相可视的，现在求三条两两互相可视的解

思路:覆盖问题，我们首先排序，然后往前找之前有没有可视的解，这样并不会影响到结果，因为这种可视是相互的，

然后因为我们线段树的单位是线段，不是点，所以我们需要将每次的值*2，这样能避免：两个相邻的点之间的空的距离被覆盖到

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <vector>
#define lson(x) ((x) << 1)
#define rson(x) ((x) << 1 | 1)
using namespace std;
const int maxn = 8005<<1;

vector<int> ve[maxn<<1];
int vis[maxn<<1];
struct seg {
	int w;
};

struct segment_tree {
	seg node[maxn<<2];

	void build() {
		memset(node, -1, sizeof(node));
	}

	void push(int pos) {
		if (node[pos].w != -1) {
			node[lson(pos)].w = node[rson(pos)].w = node[pos].w;
			node[pos].w = -1;
		}
	}

	void modify(int l, int r, int pos, int x, int y, int z) {
		if (x <= l && y >= r) {
			node[pos].w = z;
			return;
		}	
		push(pos);
		int m = l + r >> 1;
		if (x <= m)
			modify(l, m, lson(pos), x, y, z);
		if (y > m)
			modify(m+1, r, rson(pos), x, y, z);
	}

	void query(int l, int r, int pos, int x, int y, int z) {
		if (node[pos].w != -1) {
			if (!vis[node[pos].w]) {
				vis[node[pos].w] = 1;
				ve[z].push_back(node[pos].w);
			}
			return;
		}
		if (l == r)
			return;
		int m = l + r >> 1;
		if (x <= m)
			query(l, m, lson(pos), x, y, z);
		if (y > m)
			query(m+1, r, rson(pos), x, y, z);
	}
} tree;

struct segment {
	int a, b, x;
	bool operator <(const segment &tmp) const {
		return x < tmp.x;
	}
} a[maxn];

int main() {
	int t, n;
	scanf("%d", &t);
	while (t--) {
		scanf("%d", &n);
		int l = 0x3f3f3f3f, r = -1;
		for (int i = 0; i < n; i++) {
			scanf("%d%d%d", &a[i].a, &a[i].b, &a[i].x);
			a[i].a *= 2;
			a[i].b *= 2;
		}
		sort(a, a+n);
		tree.build();
		for (int i = 0; i < n; i++)
			ve[i].clear();
		for (int i = 0; i < n; i++) {
			memset(vis, 0, sizeof(vis));
			tree.query(0, maxn<<1, 1, a[i].a, a[i].b, i);
			tree.modify(0, maxn<<1, 1, a[i].a, a[i].b, i);
		}
		int ans = 0;
		for (int i = 0; i < n; i++) {
			int cnt = i;
			for (int j = 0; j < ve[cnt].size(); j++) {
				int cur = ve[cnt][j];
				for (int k = 0; k < ve[cur].size(); k++) 
					for (int l = 0; l < ve[cnt].size(); l++)
						if (ve[cur][k] == ve[cnt][l])
							ans++;
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}


联系
我们