当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

6505:Problem F. Like A Tree

题目描述
There are n segments on the two-dimensional plane. The two endpoints of ith segment is ($S_{x_i}$, $S_{y_i}$) and ($T_{x_i}$, $T_{y_i}$). All the segments are parallel to the x-axis or y-axis. These segments actually form a undirected graph with infinite nodes and edges.
We want to know whether these segments form a tree, which means: for every pair of different points on these segments, they are connected by exactly one simple path.
(In our segment-based undirected graph, a “path” is considered as a continuous infinite set of points in these segments, a “simple path” is a path that each point in the set appears only once, and two simple paths are considered to be different if and only if their corresponding point sets are different. )
输入解释
Input is given from Standard Input in the following format:
n
$S_{x_1}$ $S_{y_1}$ $T_{x_1}$ $T_{y_1}$
$S_{x_2}$ $S_{y_2}$ $T_{x_2}$ $T_{y_2}$
...
...
...
$S_{x_n}$ $S_{y_n}$ $T_{x_n}$ $T_{y_n}$
Constraints
1 ≤ n ≤ 100000
-10^9 ≤ $S_{x_i}$,$S_{y_i}$,$T_{x_i}$,$T_{y_i}$≤ 10^9(1 ≤ i ≤ n), and all coordinates are integers.
It is guaranteed that every segment meet exactly one of these two conditions:$S_{x_i}$=$T_{x_i}$,$S_{y_i}$=$T_{y_i}$
输出解释
Print one line denotes the answer.
If every pair of points in these n segments are connected by exactly one path, output “Yes”, otherwise “No”
输入样例
5
3 0 1 0
0 0 2 0
2 0 2 2
2 2 0 2
0 2 0 1
4
0 0 2 0
2 0 2 2
2 2 0 2
0 2 0 0
输出样例
Yes
No
来自杭电HDUOJ的附加信息
Recommend

该题目是Virtual Judge题目,来自 杭电HDUOJ

源链接: HDU-6505

最后修改于 2020-10-25T23:31:55+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
8000/5000MS(Java/Others) 262144/262144K(Java/Others)