#P4427. [Nwerc2015] Cleaning Pipes清理管道

    ID: 3632 传统题 1000ms 512MiB 尝试: 59 已通过: 19 难度: 4 上传者: 标签>难度分类普及+/提高-图论二分图判定计算几何线段相交叉积枚举与搜索广度优先搜索CF1600

[Nwerc2015] Cleaning Pipes清理管道

[NWERC 2015] Cleaning Pipes

题目描述

Linköping 的地下供水系统有若干水井。每条管道都是一条线段,从某口水井通往另一个地点。管道处于同一深度,两条管道的公共点只要不是水井,就是需要清理的交点。管道端点与另一条管道相接也算交点。每口井可以引出任意数量的管道。

清洁机器人从某条管道起点的水井进入,走到末端后返回,可清理沿途所有交点。所有入选管道的机器人必须同时启动。为避免碰撞,经过同一个交点的两条管道中,至多一条可以放机器人。

能否选出一些管道,使每个交点都恰好由一台机器人清理?

输入格式

第一行两个整数 w,pw,p(1≤w,p≤10001\le w,p\le1000),分别是水井数和管道数。

接下来 ww 行,每行两个整数 xi,yix_i,y_i,表示编号为 ii 的水井坐标。水井编号为 11 到 ww。

接下来 pp 行,每行三个整数 s,x,ys,x,y(1≤s≤w1\le s\le w),表示从第 ss 口水井到 (x,y)(x,y) 的一条管道。所有坐标均在 [−10000,10000][-10000,10000] 内。

每条管道只经过它起点的那口水井,且长度为正。任意两条管道至多有一个公共点,该点可以是其中一条或两条管道的端点。若一个点被三条或更多管道共享,则该点一定是水井。

输出格式

若可以按要求清理全部交点,输出 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