4574: Bracelet Crossings
Memory Limit:128 MB
Time Limit:1 S
Judge Style:Text Compare
Creator:
Submit:1
Solved:1
Description
奶牛 Bessie 喜欢手工艺。在她的空闲时间,她制作了 $N$($1\le N\le 50$)个手链,编号为 $1 \ldots N$。第 $i$ 个手链涂有颜色 $i$,是 $N$ 种不同的颜色之一。制作完手链后,Bessie 将它们放在桌子上进行展示(我们可以将其视为二维平面)。她精心布置这些手链,以满足以下三个条件:
- 每个手链是一个简单闭合折线——一组顶点(点)依次用线段连接,并且第一个点和最后一个点相同(欢迎查阅维基百科页面了解更多详情:polygonal chain,或百度百科:折线), + 没有手链与自身相交(这对应「简单」折线);以及+ 没有两条手链相交。
Sample Input Copy
5
1 2
2 1 1
2 1 1
1 3
2 1 1
0
2 1 1
2 1
4 1 2 1 2
4 2
6 1 2 2 3 3 1
6 1 2 4 4 2 1
2 2
4 1 1 2 2
4 2 2 1 1
Sample Output Copy
YES
NO
NO
YES
NO
HINT
对于第一个子测试用例,一组可行的手链位置为:
对于第四个子测试用例,一组可行的手链位置为:
## 测试点性质: + 测试点 2 满足 $N = 1$。 + 测试点 3-5 满足 $N=2$。 + 测试点 6-8 满足 $M=1$。 + 测试点 9-14 满足 $M=2$。 + 测试点 15-20 没有额外限制。 供题:Richard Qi