题目描述

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  100

typedef 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;
}