| 题目名称 | 1549. [CEPC2001]水平可见线段 |
|---|---|
| 输入输出 | visiblesegments.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 5000 ms (5 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 1 |
| 题目来源 |
 cstdio
于2014-03-20加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：5， 提交：9， 通过率：55.56% | ||||
 AAAAAAAAAA |
100 | 0.054 s | 0.99 MiB | C++ |
 KZNS |
100 | 0.107 s | 1.22 MiB | C++ |
 mikumikumi |
100 | 0.166 s | 0.90 MiB | C++ |
 cstdio |
100 | 0.206 s | 1.92 MiB | C++ |
 123 |
100 | 1.256 s | 62.35 MiB | C++ |
 @二向箔@ |
0 | 0.000 s | 13.70 MiB | C++ |
|
mikumikumi |
0 | 0.074 s | 5.27 MiB | C++ |
|
KZNS |
0 | 0.091 s | 1.22 MiB | C++ |
|
AAAAAAAAAA |
0 | 5.000 s | 61.93 MiB | C++ |
| 关于 水平可见线段 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
为什么O（N^2）的程序被卡，O（N^3）就rank1了
AAAAAAAAAA
2017-08-17 20:22
4楼
| ||||
|
因为线段的端点和中间，需要开二倍的线段树来表示端点和线段这两种东西，
被坑在两个点间可能被加了多条边上了。。。 | ||||
|
这理躺了一个被线段树坑死的人
| ||||
|
平面图中三角形……具体见WC2003刘才良论文……
| ||||
1549. [CEPC2001]水平可见线段
★★★ 输入文件：visiblesegments.in
输出文件：visiblesegments.out
简单对比时间限制：5 s 内存限制：256 MiB
【题目描述】
平面上有一些互不相交的竖直线段。如果两条线段能被一条不与任何其他竖直线段有公共点的水平线段相连，我们就称它们是水平可见的。如果三条不同的竖直线段两两水平可见，我们就称它们构成了一个三元组。给出竖直线段的集合，求三元组的个数。
【输入格式】
输入文件包含多组数据。
输入文件的第一行有一个整数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