B 村庄的牧群遭到危险!狼群正在袭击了一个牧场的羊。牧场的主人 John 决定消灭所有的狼而不伤到任何一只羊。于是他拿起了祖父留给他的步枪,冲向大屠杀。这支抢装有穿甲弹,因此,可以消灭一条直线上的任何动物,包括羊。John 站在原点 (0,0),于是每次射击为从原点出发的一条射线。如果这条射线和一个动物相交,那么这个动物就被射死。你的任务是帮 John 找到最少射击次数,使得能够消灭所有狼而不伤到羊。
第一行为n,m分别代表狼和羊的数目。
接下来n+m行,每行四个整数x_1,y_1,x_2,y_2用一条线段(x_1,y_1),(x_2,y_2) 来描述一个动物。前n行描述的是狼,后m行描述的是羊。
如果可以消灭所有狼而不伤到羊,输出最少射击次数。否则,输出No solution
。
2 1 1 1 2 3 -5 4 2 2 999 1000 1000 999
1
0\leq n,m\leq10^5; 1000\leq x_1,x_2,y_1,y_2\leq1000
注意线段之间可能相交,线段也可经过原点(该动物会被任何一次射击杀死)。