#P4427. [Nwerc2015] Cleaning Pipes清理管道
[Nwerc2015] Cleaning Pipes清理管道
[NWERC 2015] Cleaning Pipes
题目描述
Linköping 的地下供水系统有若干水井。每条管道都是一条线段,从某口水井通往另一个地点。管道处于同一深度,两条管道的公共点只要不是水井,就是需要清理的交点。管道端点与另一条管道相接也算交点。每口井可以引出任意数量的管道。
清洁机器人从某条管道起点的水井进入,走到末端后返回,可清理沿途所有交点。所有入选管道的机器人必须同时启动。为避免碰撞,经过同一个交点的两条管道中,至多一条可以放机器人。
能否选出一些管道,使每个交点都恰好由一台机器人清理?
输入格式
第一行两个整数 (),分别是水井数和管道数。
接下来 行,每行两个整数 ,表示编号为 的水井坐标。水井编号为 到 。
接下来 行,每行三个整数 (),表示从第 口水井到 的一条管道。所有坐标均在 内。
每条管道只经过它起点的那口水井,且长度为正。任意两条管道至多有一个公共点,该点可以是其中一条或两条管道的端点。若一个点被三条或更多管道共享,则该点一定是水井。
输出格式
若可以按要求清理全部交点,输出 possible;否则输出 impossible。
样例 #1
样例输入 #1
3 3
0 0
0 2
2 0
1 2 3
2 2 2
3 0 3
样例输出 #1
impossible
样例 #2
样例输入 #2
2 3
0 0
0 10
1 5 15
1 2 15
2 10 10
样例输出 #2
possible