1340: 运河贸易桥梁规划问题(必做)
Memory Limit:128 MB
Time Limit:1.000 S
Judge Style:Text Compare
Creator:
Submit:62
Solved:54
Description
在东方大陆有一条东西走向的运河,运河两岸是笔直的南北河岸,岸上各有 N 个不同的贸易港口。已知北岸每个港口恰好有一个位于南岸的友好贸易港,且不同北岸港口的友好港互不重复。
每对友好贸易港向商会申请在运河上修建一座直线桥梁连接双方,但由于运河上货船频繁,商会规定任意两座桥梁不得交叉,以确保航行安全。请设计方案,在满足桥梁不交叉的前提下,求出最多可修建的桥梁数量。
Input
第一行一个整数 N(1 ≤ N ≤ 5000),表示港口数量。
第 2 行到第 N+1 行,每行包含两个整数 A 和 B,分别表示南岸和北岸某对友好贸易港的坐标(0 ≤ A,B ≤ 10000)。
Output
仅一行,输出一个整数,表示最多可修建的桥梁数量。
Sample Input Copy
7
22 4
2 6
10 3
15 12
9 8
17 17
4 2
Sample Output Copy
4