OI题库

【题目描述】

平面上有一些互不相交的竖直线段。如果两条线段能被一条不与任何其他竖直线段有公共点的水平线段相连，我们就称它们是水平可见的。如果三条不同的竖直线段两两水平可见，我们就称它们构成了一个三元组。给出竖直线段的集合，求三元组的个数。

【输入格式】

输入文件包含多组数据。

输入文件的第一行有一个整数d，代表数据组数，1<=d<=20.接下来是d组数据。

每组数据的第一行有一个整数n（1<=n<=8000），代表竖直线段的条数。

接下来的n行每行有3个由空格分隔的非负整数：yi',yi'',xi，分别代表起点和终点的y坐标和线段的x坐标。坐标范围为[0,8000]。这些竖直线段互不相交。

【输出格式】

对每组数据输出一行，共d行。

第i行包含一个整数，即第i组数据中的三元组数。

【样例输入】

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

【样例输出】

1

【来源】

ACM Central European Programming Contest,Warsaw 2001,Poland: Problem H: Horizontally visible segments

POJ 1436