#1722. 友好城市

友好城市

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

一条河从东向西流过,并把魔法世界分为南北两个部分。河的两岸各有 n\red{n}个城市,且北岸的每一个城市都与南岸的某个城市是友好城市,而且对应的关系 是一一对应的,如图所示。

img

现在要求在两个友好城市之间建立一条航线,但为了安全起见,所有航线都不 能相交,因此,不是所有的友好城市都能建立航线。请问,最多能建多少航线?

输入格式

第一行两个由空格分隔的整数x,y,10\red{x,y,10≤}x\red{x≤}6000,10\red{6 000,10≤}y\red{y≤}100\red{100}x\red{x}表示河的 长度而y\red{y}表示宽,第二行是一个整数n(1\red{n(1≤}n\red{n≤}5000),\red{5 000),}表示分布在河两岸的城市对 数。接下来的n\red{n}行每行有两个由空格分隔的正数c,d(c,d\red{c,d(c,d≤}x),\red{x),}描述每一对友好 城市与河起点的距离,c\red{c}表示北岸城市的距离,而d\red{d}表示南岸城市的距离。在河的 同一边,任何两个城市的位置都是不同的。

输出格式

在安全条件下能够开通的最大航线数目。

样例

输入样例

30 4
5
4 5
2 4
5 2
1 3
3 1

输出样例

3

添胜提高班day6

未参加
状态
已结束
规则
IOI
题目
7
开始于
2023-8-6 14:00
结束于
2023-8-7 11:00
持续时间
21 小时
主持人
参赛人数
23