题目描述:
一个左下角为(0,0) ,右上角为(A,A)的正方形内,里面有 N 个坐标均为整数的点 。
现在要求每个点都连一条与坐标轴平行的线段到边界上, 任意线段不能包含其它点,且线段之间不能有相交或者接触。求所有线段最小的总长度。
输入格式:
输入的第一行为一个整数 A。
输入的第二行为一个整数 N,表示正方形内有 N 个点。
接下来共 N 行,每行两个整数(x,y) ,保证每个点的坐标不一样。
输出格式:
输出仅一个数字,表示线段的最小总长度。数据保证有解。
输入样例 1:
6
4
3 1
3 5
5 4
1 4
输出样例 1:
4
输入样例 2:
10
5
8 1
4 3
1 2
3 9
8 5
输出样例 2:
8
输入样例 3:
10
4
5 1
5 2
4 3
6 3
输出样例 3:
13
数据范围:
对于 100%的数据,2<=A<=30,1<=N<=100,1<=x,y<=A-1
一个左下角为(0,0) ,右上角为(A,A)的正方形内,里面有 N 个坐标均为整数的点 。
现在要求每个点都连一条与坐标轴平行的线段到边界上, 任意线段不能包含其它点,且线段之间不能有相交或者接触。求所有线段最小的总长度。
输入格式:
输入的第一行为一个整数 A。
输入的第二行为一个整数 N,表示正方形内有 N 个点。
接下来共 N 行,每行两个整数(x,y) ,保证每个点的坐标不一样。
输出格式:
输出仅一个数字,表示线段的最小总长度。数据保证有解。
输入样例 1:
6
4
3 1
3 5
5 4
1 4
输出样例 1:
4
输入样例 2:
10
5
8 1
4 3
1 2
3 9
8 5
输出样例 2:
8
输入样例 3:
10
4
5 1
5 2
4 3
6 3
输出样例 3:
13
数据范围:
对于 100%的数据,2<=A<=30,1<=N<=100,1<=x,y<=A-1