410598: GYM104064 F Flatland Olympics

F. Flatland Olympicstime limit per test4 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

It is the day after Olympia, and you—as the organizer—are happy that everything worked well in these troublesome times. Well, not everything....

Since this morning e-mails have been filling up your inbox, containing complaints about obscured views during the most important race: the $$$100$$$-meter dash. They demand their money back, or threaten exposing you on social media. To make things worse, spectators have not just complained once, but they have sent you a separate e-mail for every person that blocked their view at some point during the race! They even wrote multiple e-mails when two or more people blocked their view at the same time. And not only that, some visitors complained to the main sponsor Dy & Son who in turn has urged you to improve the situation.

Since you expect that a greater number of visitors will be allowed to spectate at the next Olympic games, you assume that there will be even more complaints if you do not address this issue. If the situation will be too bad, you may even lose your sponsor Dy & Son. Therefore, you decide to count the number of complaints beforehand. To do this, you model the running track as a straight line segment, and count the maximal number of complaints you could get based on the seating of the visitors. Depending on the number of complaints you expect, you will determine if you need to rework the seating or just reconfigure your spam blocker and try to find a new sponsor.

Illustration of Sample Input 2. The running track is drawn as a red line and the seats of the visitors are highlighted in blue. The second visitor will complain about the first visitor and the fourth visitor will complain about the third visitor. Input

The input consists of:

• One line containing four integers $$$x_s$$$, $$$y_s$$$, $$$x_e$$$ and $$$y_e$$$ $$$(|x_s|, |y_s|, |x_e|, |y_e| \leq 10^9)$$$, where $$$s=(x_s, y_s)$$$ is the starting point of the running track and $$$e=(x_e, y_e)$$$ is the end point of the running track. Both $$$s$$$ and $$$e$$$ belong to the running track.
• One line containing an integer $$$n$$$ $$$(1 \leq n \leq 10^{5})$$$, the number of visitors.
• $$$n$$$ lines, each containing two integers $$$x$$$ and $$$y$$$ $$$(|x|,|y|\leq 10^{9})$$$, where $$$(x,y)$$$ is the location of the seat of a visitor.

It is guaranteed that the track has a positive length, i.e. $$$s\neq e$$$. Further, you can assume that all visitors are seated at distinct locations and that no visitor is seated on the track.Output

Output the total number of complaints that you would receive for the given seating.

ExamplesInput

0 0 100 0
4
50 20
50 30
50 50
120 0

Output

3

Input

0 0 100 0
5
50 20
50 30
50 -20
50 -30
100 30

Output

2