网站建设 6万,杭州置地电商基地网站建设,正品购物平台哪个最好,php制作网页教程题目 Al识别到面板上有N(1N≤100)个指示灯#xff0c;灯大小一样#xff0c;任意两个之间无重叠。由于AI识别误差#xff0c;每次识别到的指示灯位置可能有差异#xff0c;以4个坐标值描述Al识别的指示灯的大小和位置(左上角x1,y1#xff0c;右下角x2.y2)。请输出先行…题目 Al识别到面板上有N(1N≤100)个指示灯灯大小一样任意两个之间无重叠。由于AI识别误差每次识别到的指示灯位置可能有差异以4个坐标值描述Al识别的指示灯的大小和位置(左上角x1,y1右下角x2.y2)。请输出先行后列排序的指示灯的编号排序规则: 每次在尚未排序的灯中挑选最高的灯作为基准灯 找出和基准灯属于同一行所有的灯进行排序。两个灯高低偏差不超过灯半径算同一行(即两个灯坐标的差灯高度的一半)。 输入描述 第一行为N表示灯的个数 接下来N行每行为1个灯的坐标信息格式为:编号 x1 y1 x2 y2 1∶编号全局唯一 2:1编号≤100 3: 0x1 x2 ≤ 1000 4: 0y1 y2 ≤ 1000 输出描述 排序后的编号列表编号之间以空格分隔 示例1: 输入 5 1 0 0 2 2 2 6 1 8 3 3 3 2 5 4 5 5 4 7 6 4 0 4 2 6 输出 1 2 3 4 5 思路 本题描述比较复杂不好理解下面转化为好理解的版本。 先找到基准灯所有灯中最高的等高时取最左边的 找到所有与基准灯为同一行的灯按照从左到右的顺序排序 继续再剩余未排序的灯中找基准灯重复上述过程。 在实现思路上我们已经有灯的左上角及右下角坐标那么我们可以算出每个灯的中心坐标以及半径假设以(XY)表示中心坐标以R表示半径。 由于涉及到复杂对象的比较我们可以新建一个灯对象Lamp它有三个属性X代表中心点横坐标Y代表中心点的纵坐标R代表半径。将每行输入转为一个灯并放入集合list中为了寻找基准灯也就是最高和最左边的灯可以对Lamp对象自定义比较方法取Y最小的Y相等时取X最小的对list按照我们自定义规则进行排序最高最左的在前对排序后list的第一个灯作为基准灯找到和基准灯在同一行的灯。判断同一行的标准两个灯纵坐标的差值的绝对值灯半径。这个比较方法可以直接写在我们新建的Lamp对象中。对与基准灯同一行的灯加入到一个临时集合tmp然后再对tmp排序按从左到右排序即可X越小排在越前将本轮排序结果tmp加入最终的ans中继续寻找下一个基准灯还未被加入到ans中的里面找最高最左的灯重复4567步骤。 题解
package hwod;import java.util.*;public class AIBoardRecognize {public static void main(String[] args) {Scanner sc new Scanner(System.in);int n sc.nextInt();int[][] matrix new int[n][5];for (int i 0; i n; i) {for (int j 0; j 5; j) {matrix[i][j] sc.nextInt();}}ListLamp res aIBoardRecognize(matrix);for (int i 0; i res.size(); i) {if (i ! 0) System.out.print( );System.out.print(res.get(i).getId());}}private static ListLamp aIBoardRecognize(int[][] matrix) {int m matrix.length;ListLamp lamps new ArrayList(m);for (int i 0; i m; i) {int id matrix[i][0];int x (matrix[i][1] matrix[i][3]) 1;int y (matrix[i][2] matrix[i][4]) 1;int r (matrix[i][3] - matrix[i][1]) 1;lamps.add(new Lamp(id, x, y, r));}Collections.sort(lamps);ListLamp ans new ArrayList(m);int i 0;while (i m) {Lamp base lamps.get(i);ListLamp tmp new ArrayList();while (i m base.isSameHigh(lamps.get(i))) {tmp.add(lamps.get(i));i;}Collections.sort(tmp, (o1, o2) - o1.getX() - o2.getX());ans.addAll(tmp);}return ans;}
}class Lamp implements ComparableLamp {private int id;private int x;private int y;private int r;public Lamp(int id, int x, int y, int r) {this.id id;this.x x;this.y y;this.r r;}public int getId() {return id;}public int getX() {return x;}public int getY() {return y;}public int getR() {return r;}public boolean isSameHigh(Lamp lamp) {return Math.abs(lamp.getY() - this.getY()) this.r;}Overridepublic int compareTo(Lamp other) {return this.getY() other.getY() ? this.getX() - other.getX() : this.getY() - other.getY();}
}为了方便验证这里再提供三组测试用例 用例1 5 1 0 0 2 2 2 6 0 8 2 3 3 1 5 3 5 5 1 7 3 4 0 4 7 6 输出 1 3 5 2 4 用例2 5 1 0 0 2 2 2 6 0 8 2 3 3 1 5 3 5 5 2 7 4 4 0 4 7 6 输出 1 3 2 5 4 用例3 5 1 0 0 2 2 2 6 0 8 2 3 3 1 5 3 5 5 3 7 5 4 0 4 7 6 输出 1 3 2 4 5
