如何优化求解矩形缺失顶点坐标的Java算法以适配全部合法输入?
已知矩形三顶点求第四顶点的Java算法优化
问题场景
给定3个按换行分隔的xy平面坐标,单个坐标的x、y值以空格分隔,这3个坐标是平面内某矩形的3个顶点,要求算法返回能和这三个点共同构成完整矩形的第4个顶点。
- 示例输入:依次输入
5 5、5 7、7 5 - 对应正确输出:
7 7
目前可运行的Java实现仅能跑通上述示例,更换其他合法输入的三顶点组合就会输出错误结果,且难以定位bug。在输入保证是矩形三个合法顶点的前提下,需要调整算法实现,覆盖所有合法输入场景。
原有问题代码如下:
import java.io.*; public class cetvrta { public static void main(String[] args) throws IOException { BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); String point1 = reader.readLine(); String point2 = reader.readLine(); String point3 = reader.readLine(); String[] cord1 = point1.split(" "); String[] cord2 = point2.split(" "); String[] cord3 = point3.split(" "); int x4 = 0; int y4 = 0; int x1 = Integer.parseInt(cord1[0]); int y1 = Integer.parseInt(cord1[1]); int x2 = Integer.parseInt(cord2[0]); int y2 = Integer.parseInt(cord2[1]); int x3 = Integer.parseInt(cord3[0]); int y3 = Integer.parseInt(cord3[1]); if (y1 == y2) { if (x3 == x1) { x4 = x2; y4 = y3; } if (x3 == x2) { x4 = x1; y4 = y3; } } if (y3 == y2) { if (x2 == x3) { x4 = x1; y4 = y2; } if (x2 == x1) { x4 = x3; y4 = y2; } } if (y1 == y3) { if (x2 == x1) { x4 = x3; y4 = y2; } if (x2 == x3) { x4 = x1; y4 = y2; } } System.out.println(x4 + " " + y4); } }
原有代码的bug根源
- 硬编码枚举了固定顺序的点排列组合判断分支,没有覆盖所有可能的输入顺序。比如输入点顺序为
3 4、1 2、3 2时,所有判断分支都无法匹配到赋值逻辑,程序直接保留x4、y4的初始值0,输出错误结果 - 所有判断分支没有做互斥处理,多分支条件同时满足时,后执行的if会直接覆盖前面计算好的坐标值,导致最终结果出错
- 算法逻辑没有利用平行坐标轴矩形的坐标分布规律,靠穷举判断的方式本身就容易漏场景
改进实现思路
针对边平行于坐标轴的矩形,所有顶点的x坐标只会出现两个不同值,每个值恰好出现2次;y坐标同理,也是两个不同值各出现2次。在已知3个顶点的前提下,必然有一个x值只在三个点里出现1次,剩下两个x值是相等的;y坐标也符合这个规律。
- 利用异或运算的特性:
a ^ a = 0、a ^ 0 = a,三个数连续异或后,出现两次的相等数会抵消为0,剩下的结果就是那个只出现1次的数 - 不需要做复杂的分支判断,直接对三个x值做异或得到第4个点的x坐标,对三个y值做异或得到第4个点的y坐标,就能覆盖所有输入顺序的合法场景
改进后的正确代码
import java.io.*; public class cetvrta { public static void main(String[] args) throws IOException { BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); String point1 = reader.readLine(); String point2 = reader.readLine(); String point3 = reader.readLine(); String[] cord1 = point1.split(" "); String[] cord2 = point2.split(" "); String[] cord3 = point3.split(" "); int x1 = Integer.parseInt(cord1[0]); int y1 = Integer.parseInt(cord1[1]); int x2 = Integer.parseInt(cord2[0]); int y2 = Integer.parseInt(cord2[1]); int x3 = Integer.parseInt(cord3[0]); int y3 = Integer.parseInt(cord3[1]); // 利用异或特性找出仅出现一次的坐标值 int x4 = x1 ^ x2 ^ x3; int y4 = y1 ^ y2 ^ y3; System.out.println(x4 + " " + y4); } }
注:该实现适配所有边平行于坐标轴的矩形输入场景,只要三个输入点是该矩形的三个合法顶点,无论点的输入顺序如何,都能输出正确的第四顶点坐标。
内容的提问来源于stack exchange,提问作者fpm21
相关产品推荐
相关产品推荐

