友好城市

题目内容

题目描述

P国有一条横贯东西的大河,河有笔直的南北两岸,岸上各有位置不同的N个城市。北岸的每个城市有且仅有一个友好城市在南岸,而且不同城市的友好城市不相同。

每对友好城市都向政府申请在河上开辟一条直线航道连接两个城市,但是由于河上雾太大,政府决定避免任意两条航道交叉,以避免事故。要求编程帮助政府做一些批准和拒绝申请的决定,使得在保证任意两条航线不相交的情况下,被批准的申请尽量多。

输入描述

第1行一个正整数N,表示城市数目,满足N<=2000。

第2行到第n+1行,每行两个正整数,中间用1个空格隔开,分别表示北岸和南岸的一对友好城市的坐标,坐标最大值不超过10000。

输出描述

仅1行,输出一个正整数,表示政府所能批准的最多申请数。

样例输入

7 22 4 2 6 10 3 15 12 9 8 17 17 4 2

样例输出

4

提示

提交评测
请登录后再操作

题目描述

友好城市
1106
0
Level2
216
109
50%
证书查询 x
请输入证书编号:

请输入正确的证书编号

学员姓名:孙兴民

课程:Scratch Level 1

发证日期:2019.08.15

证书查询

该证书不存在