QOJ.ac

QOJ

Time Limit: 4 s Memory Limit: 2048 MB Total points: 100

#2297. 平地奥林匹克

Statistics

奥林匹克运动会结束后的第二天,作为组织者的你很高兴在这些困难时期一切都进展顺利。好吧,并非一切都如此……

从今天早上开始,你的收件箱就被投诉邮件塞满了,内容都是关于在最重要的比赛——百米赛跑期间视线受阻的问题。他们要求退款,或者威胁要在社交媒体上曝光你。更糟糕的是,观众不仅投诉了一次,而且他们为比赛过程中视线受阻的每一个人都单独发送了一封电子邮件!当两个或更多人在同一时间挡住他们的视线时,他们甚至会写多封电子邮件。不仅如此,一些观众还向主要赞助商 Dy & Son 投诉,后者反过来敦促你改善这种情况。

由于你预计在下一届奥运会上将有更多的观众入场,你认为如果不解决这个问题,投诉将会更多。如果情况变得太糟糕,你甚至可能会失去赞助商 Dy & Son。因此,你决定提前计算投诉的数量。为此,你将跑道建模为一条线段,并根据观众的座位安排计算你可能收到的最大投诉数量。根据你预期的投诉数量,你将决定是需要重新规划座位,还是仅仅重新配置垃圾邮件过滤器并尝试寻找新的赞助商。

输入格式

输入包含: 一行,包含四个整数 $x_s, y_s, x_e$ 和 $y_e$ ($|x_s|, |y_s|, |x_e|, |y_e| \le 10^9$),其中 $s = (x_s, y_s)$ 是跑道的起点,$e = (x_e, y_e)$ 是跑道的终点。$s$ 和 $e$ 均属于跑道。 一行,包含一个整数 $n$ ($1 \le n \le 10^5$),即观众人数。 * $n$ 行,每行包含两个整数 $x$ 和 $y$ ($|x|, |y| \le 10^9$),其中 $(x, y)$ 是观众的座位位置。

保证跑道长度为正,即 $s \neq e$。此外,你可以假设所有观众的座位位置各不相同,且没有观众坐在跑道上。

输出格式

输出你针对给定的座位安排所收到的投诉总数。

图 F.1:样例输入 2 的示意图。跑道用红线绘制,观众的座位用蓝色高亮显示。第二位观众会投诉第一位观众,第四位观众会投诉第三位观众。

样例

样例输入 1

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

样例输出 1

3

样例输入 2

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

样例输出 2

2

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.