请用C++帮我做这道题给出思路代码和做法正确性证明代码要有注释:n在一个二维空间内有n个点它们的坐标分别是x_1y_1x_2y_2x_ny_n。n接着从平面任选一点作为新的坐标系的原点向任意两个不一定垂直于原坐标轴的方向作出新坐标系的xy轴两轴互相垂直从新坐标系的原点出发只能向新坐标系的xy轴的正方向移动产生一条路径。这条路径最多经过几个点?n第一行输入一个数n。接下来的n行每行输入x_iy_i表示第i个点的坐标。n输出一个整数ans表示路径经过的点数的最大值。n样例输入1:n4n0-0n1-0
思路:
对于每个点,我们都可以把它当做新坐标系的原点,然后枚举两个方向(即新坐标系的 x',y' 轴),然后从原点开始沿着这两个方向分别走,记录经过的点的个数,最后取最大值即可。
步骤:
-
读入 n 和 n 个点的坐标。
-
枚举每个点作为新坐标系的原点,同时枚举两个方向。
-
对于每个方向,按照坐标大小排序,然后从原点开始依次向正方向移动,记录经过的点的个数。
-
取两个方向中经过点数的最大值,更新答案。
-
输出答案。
代码及注释:
原文地址: https://www.cveoy.top/t/topic/pYP 著作权归作者所有。请勿转载和采集!