[编程题]上升点列【point】题目描述在一个二维平面内，给定 n nn 个整数点 ( x i , y i ) (x_i, y_i)(x i ,y i )，此外你还可以自由添加 k kk 个

题目信息

题目类型: 入门级
题目年份: 2022

题目题型: 编程题
关键词: 上升点列

题目题干

上升点列【point】
题目描述
在一个二维平面内，给定 n nn 个整数点 ( x i , y i ) (x_i, y_i)(x
i

,y
i

)，此外你还可以自由添加 k kk 个整数点。

你在自由添加 k kk 个点后，还需要从 n + k n + kn+k 个点中选出若干个整数点并组成一个序列，使得序列中任意相邻两点间的欧几里得距离恰好为 1 11 而且横坐标、纵坐标值均单调不减，即 x i + 1 − x i = 1 , y i + 1 = y i x_{i+1} - x_i = 1, y_{i+1} = y_ix
i+1

−x
i

=1,y
i+1

=y
i

或 y i + 1 − y i = 1 , x i + 1 = x i y_{i+1} - y_i = 1, x_{i+1} = x_iy
i+1

−y
i

=1,x
i+1

=x
i

。请给出满足条件的序列的最大长度。

输入格式
第一行两个正整数 n , k n, kn,k 分别表示给定的整点个数、可自由添加的整点个数。

接下来 n nn 行，第 i ii 行两个正整数 x i , y i x_i, y_ix
i

,y
i

表示给定的第 i ii 个点的横纵坐标。

输出格式
输出一个整数表示满足要求的序列的最大长度。

样例 #1
样例输入 #1
8 2
3 1
3 2
3 3
3 6
1 2
2 2
5 5
5 3
1
2
3
4
5
6
7
8
9
样例输出 #1
8
1
样例 #2
样例输入 #2
4 100
10 10
15 25
20 20
30 30
1
2
3
4
5
样例输出 #2
103
1
提示
【样例 #3】

见附件中的 point/point3.in 与 point/point3.ans。

第三个样例满足 k = 0 k = 0k=0。

【样例 #4】

见附件中的 point/point4.in 与 point/point4.ans。
$上升点列【point】题目描述在一个二维平面内，给定 n nn 个整数点 ( x i , y i ) (x_i, y_i)(x i ,y i )，此外你还可以自由添加 k kk 个整数点。你在自由添加 k kk 个点后，还需要从 n + k n + kn+k 个点中选出若干个整数点并组成一个序列，使得序列中任意相邻两点间的欧几里得距离恰好为 1 11 而且横坐标、纵坐标值均单调不减，即 x i + 1 − x i = 1 , y i + 1 = y i x_{i+1} - x_i = 1, y_{i+1} = y_ix i+1 −x i =1,y i+1 =y i 或 y i + 1 − y i = 1 , x i + 1 = x i y_{i+1} - y_i = 1, x_{i+1} = x_iy i+1 −y i =1,x i+1 =x i 。请给出满足条件的序列的最大长度。输入格式第一行两个正整数 n , k n, kn,k 分别表示给定的整点个数、可自由添加的整点个数。接下来 n nn 行，第 i ii 行两个正整数 x i , y i x_i, y_ix i ,y i 表示给定的第 i ii 个点的横纵坐标。输出格式输出一个整数表示满足要求的序列的最大长度。样例 #1 样例输入 #1 8 2 3 1 3 2 3 3 3 6 1 2 2 2 5 5 5 3 1 2 3 4 5 6 7 8 9 样例输出 #1 8 1 样例 #2 样例输入 #2 4 100 10 10 15 25 20 20 30 30 1 2 3 4 5 样例输出 #2 103 1 提示【样例 #3】见附件中的 point/point3.in 与 point/point3.ans。第三个样例满足 k = 0 k = 0k=0。【样例 #4】见附件中的 point/point4.in 与 point/point4.ans。$

答案解析

提示声明

免责声明：本站资源均来自网络或者用户投稿，仅供用于学习和交流：如有侵权联系删除!
温馨提示：本文属于积分文章，需要充值获得积分或升级VIP会员，也可在会员中心投稿获取。

上升点列【point】题目描述在一个二维平面内，给定 n nn 个整数点 ( x i , y i ) (x_i, y_i)(x i ,y i )，此外你还可以自由添加 k kk 个

目录

题目信息

题目题干

答案解析

相关题目

提示声明

猜你喜欢

©2016-2021 100150.com

帮助中心

上升点列【point】 题目描述 在一个二维平面内，给定 n nn 个整数点 ( x i , y i ) (x_i, y_i)(x i ​ ,y i ​ )，此外你还可以自由添加 k kk 个

目录

题目信息

题目题干

答案解析

相关题目

提示声明

猜你喜欢

©2016-2021 100150.com

帮助中心

上升点列【point】题目描述在一个二维平面内，给定 n nn 个整数点 ( x i , y i ) (x_i, y_i)(x i ,y i )，此外你还可以自由添加 k kk 个