buckbeak-escape

Buckbeak was a Hippogriff. He lived with Rubeus Hagrid and many other Hippogriff, but was later sentenced to death as he attacked Draco Malfoy after being taunted and provoked by him. Buckbeak was sentenced to death by the Committee for the Disposal of Dangerous Creatures, most of whom had been threatened by Lucius Malfoy, Draco's father, into voting for that verdict.

[Image Source]
Walden Macnair came to the Hogwarts grounds to carry out the execution, and Buckbeak was tied in Hagrid's pumpkin patch to await his death. However, using a Time-Turner, Harry Potter and Hermione Granger are here to rescue Buckbeak just prior to the execution. They are waiting behind the bushes for the right time to free Buckbeak.

They notice that Buckbeak has been tied using an unbreakable chain wound across many pillars. Heromoine knows a spell Deprimo! which can dig the pillars deep in ground for sure but will not affect the chain, hence to free Buckbeak they must force the required number of pillars to get dug into ground using this spell.

The problem they face is that casting this spell perfectly takes a significant amount of time and being short of time, they must cast this spell as few times as possible and that too without a failure to avoid being caught by Walden Macnair.

Given the top view of Hagrid's pumpkin patch your task is to determine the minimum number of times they must cast this spell without failure to help Buckbeak escape.

NOTE: By casting *Deprimo! once successfully, they can force only a single pillar to disappear into the ground. To remove multiple pillars, they must cast this spell multiple times.*
You are given the description of the top view in co-ordinate (x, y)
   form.
All the pillars are in a vertical line and have same 'x'
   co-ordinate.
Buckbeak's co-ordinates (bx, by) are to right of this vertical
   line.
Description of the chain is given in line segment form and the very
   first segment starts from (bx, by) (i.e. Buckbeak's position) and
   ends too at same position.
The chain might cross and overlap at their endpoints but it
   is assured that no pillar will fall on any line segment.Input
Line 1 # 4 space separated integers: N, M, bx, by

'N' is the number of pillars.

'M' is the number of segments.

'bx' and 'by' are the position co-ordinates of Buckbeak.

Line 2...1+N # Line i+1 contains the x and y co-ordinates of i'th pillar.

Lines 2+N...2+N+M # Each M+1 lines contains, in sequence, space separated co-ordinates x and y of a point along the chain. The first and last points describe the position of Buckbeak i.e. (bx, by).

Output
A single integer that tells the minimum number of times Harry and Hermione must cast the spell Deprimo! without failure to help Buckbeak escape.

Constraints
1 ≤ N ≤ 10

3 ≤ M ≤ 10^4

0 ≤ x < bx ≤10^4

0 ≤ y, by ≤10^4

SAMPLE INPUT
2 10 7 2
3 4
3 2
7 2
3 5
2 2
3 1
4 2
2 4
6 5
4 1
1 2
4 3
7 2

SAMPLE OUTPUT
1

Explanation

Two pillars are placed at location (3, 4) and (3, 2). 
Buckbeak is at position (7, 2).
The chain starts at Buckbeak's position goes to (3, 5) --> (2,2) and so on finally meeting at (7, 2) again. The shape is the same as the figure given above.

As you can see removing any of the pillars will allow Buckbeak to escape.Hence Harry and Hermione need to cast the spell only once.

Source: hackerearth | Difficulty: EASY


Solutions: