【AI面板识别】

题目描述

AI识别到面板上有N（1 ≤ N ≤ 100）个指示灯，灯大小一样，任意两个之间无重叠。

由于AI识别误差，每次别到的指示灯位置可能有差异，以4个坐标值描述AI识别的指示灯的大小和位置(左上角x1,y1，右下角x2,y2)，

请输出先行后列排序的指示灯的编号，排序规则：

1. 每次在尚未排序的灯中挑选最高的灯作为的基准灯，
2. 找出和基准灯属于同一行所有的灯进行排序。两个灯高低偏差不超过灯半径算同一行（即两个灯坐标的差 ≤ 灯高度的一半）。

C语言代码

#define  _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include"math.h"
#include"string.h"
#include"stdlib.h"
#define MAX_LIGHTS  100typedef struct {int id;int x;int y;int r;
}Light;int compareByY(const void* a, const void* b)
{return ((Light*)a)->y - ((Light*)b)->y;
}
int compareByX(const void* a, const void* b)
{return ((Light*)a)->x - ((Light*)b)->x;
}int main()
{int n;Light lights[MAX_LIGHTS];Light rowLights[MAX_LIGHTS];scanf("%d", &n);for (int i = 0; i < n; i++){int id, x1, y1, x2, y2;scanf("%d %d %d %d %d", &id, &x1, &y1, &x2, &y2);int cx = (x1 + x2) / 2;int cy = (y1 + y2) / 2;int rad = (x2 - x1) / 2;lights[i] = {id,cx,cy,rad};}qsort(lights, n, sizeof(Light), compareByY);//int result[MAX_LIGHTS];int resultIndex = 0;int i = 0;while (i < n){int rowCount = 0;Light ref = lights[i];rowLights[rowCount++] = ref;i++;while (i < n && abs(lights[i].y - ref.y) <= ref.r) {rowLights[rowCount++] = lights[i];i++;}qsort(rowLights, rowCount, sizeof(Light), compareByX);for (int j = 0; j < rowCount; j++) {result[resultIndex++] = rowLights[j].id;}}for (int i = 0; i < resultIndex; i++) {printf("%d ", result[i]);}printf("\n");return 0;
}