349. Wolves and Sheep

Time limit per test: 0.5 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard

The herds of Berland are in danger! Wolves have attacked a pasture of sheep. The shepherd has decided to exterminate wolves in the neighborhood without causing any damage to the sheep. Thus he took a trophy gun, left to him by his grandfather and headed for the ambush. The gun is cast steel and fires with the armour-piercing shells, and the bullets go right through and can hurt a sheep if a wolf is being shot. The wolves and the sheep are represented by segments. The shepherd is in point (0, 0). The flying path of a bullet is a ray coming from point (0, 0). If the path and the segment, characterizing an animal, intersect — the animal dies. Please find the minimum of shots, that is necessary, to kill all the wolves. We rely upon your prudence, for every sheep should remain safe and sound.

The first line describes two integers N and M (0 ≤ N ≤ 105; 0 ≤ M ≤ 105) — is the amount of the wolves and the sheep accordingly. It is followed by N + M lines. Every line contains four integer numbers X1, Y1, X2, Y2 (-1000 ≤ X1, X2 ≤ 1000; 1 ≤ Y1, Y2 ≤ 1000), describing the segments. The first N lines describe the disposition of the wolves, the following M lines reveal the situation with the sheep. Segments can degenerate to points.

Print the minimum amount of shots required to kill all the wolves. If you find this request quite impossible to fulfill without killing a single sheep, enter "No solution" (no quotation marks).

sample input
sample output
1 1
5 5 6 7
3 5 8 5
No solution

sample input
sample output
2 1
1 1 2 3
-5 4 2 2
999 1000 1000 999

Online Contester Team © 2002 - 2010. All rights reserved.