BZPRO
#3904. 狼和羊
内存限制：512 MiB
时间限制：40 Sec
提交
提交记录
讨论
题目描述
B 村庄的牧群遭到危险！狼群正在袭击了一个牧场的羊。牧场的主人 John 决定消灭所有的
狼而不伤到任何一只羊。于是他拿起了祖父留给他的步枪，冲向大屠杀。这支抢装有穿甲弹，因
此，可以消灭一条直线上的任何动物，包括羊。John 站在原点 (0, 0)，于是每次射击为从原点出
发的一条射线。如果这条射线和一个动物相交，那么这个动物就被射死。你的任务是帮 John 找
到最少射击次数，使得能够消灭所有狼而不伤到羊。
输入格式
第一行为 n,m分别代表狼和羊的数目。接下来n+m行，每行四个整数 x1,y1,x2,y2 用一
条线段 (x1,y1) (x2,y2) 来描述一个动物。前 n行描述的是狼，后m行描述的是羊。
输出格式
如果可以消灭所有狼而不伤到羊，输出最少射击次数。否则，输出”No solution”（不含引
号）。
样例
样例输入
2 1
1 1 2 3
-5 4 2 2
999 1000 1000 999
样例输出
1
数据范围与提示
对于 100% 的数据，0 <= n,m<= 10^5; 1000 <= x1,x2,y1,y2 <= 1000，注意线段之间可能相交，
线段也可经过原点（该动物会被任何一次射击杀死）。
BZPRO