C语言 | Leetcode C语言题解之第391题完美矩形

题目：

题解：

/* 参照官方答案题解：
1.小矩形面积之和等于大矩形区域面积
2.矩形区域内部顶点出现次数只能是2次或4次（边界四个顶点只能出现一次）
*/
typedef struct {
    int x;
    int y;
} Coordinate;

typedef struct {
    Coordinate pos;
    int cnt;
    UT_hash_handle hh;
} CoordRecord;

CoordRecord *FindNode(CoordRecord **root, int x, int y)
{
    Coordinate tmp = {
        .x = x,
        .y = y
    };
    CoordRecord *ptr = NULL;
    HASH_FIND(hh, *root, &tmp, sizeof(Coordinate), ptr);
    return ptr;
}

void AddNode(CoordRecord **root, int x, int y)
{
    CoordRecord *ptr = FindNode(root, x, y);
    if (ptr == NULL) {
        CoordRecord *rec = (CoordRecord*)malloc(sizeof(CoordRecord));
        rec->cnt = 1;
        rec->pos.x = x;
        rec->pos.y = y;
        HASH_ADD(hh, *root, pos, sizeof(Coordinate), rec);
    } else {
        (ptr->cnt)++;
    }
}

bool isRectangleCover(int** rectangles, int rectanglesSize, int* rectanglesColSize){
    CoordRecord *root = NULL;
    int minx = INT_MAX;
    int miny = INT_MAX;
    int maxa = 0;
    int maxb = 0;
    int area = 0;
    for (int i = 0; i < rectanglesSize; ++i) {
        int x = rectangles[i][0];
        int y = rectangles[i][1];
        int a = rectangles[i][2];
        int b = rectangles[i][3];

        /* 计算每个小矩形的面积之和 */
        area += (a - x) * (b - y);

        /* 为最后求大矩形面积做准备 */
        minx = fmin(minx, x);
        miny = fmin(miny, y);
        maxa = fmax(maxa, a);
        maxb = fmax(maxb, b);

        /* 统计每个顶点出现的次数 */
        AddNode(&root, x, y);
        AddNode(&root, x, b);
        AddNode(&root, a, y);
        AddNode(&root, a, b);
    }

    /* 面积之和不相等，则返回false */
    if ((maxa - minx) * (maxb - miny) != area) {
        return false;
    }

    /* 判断每个顶点出现的次数 */
    HASH_ITER(hh, root, node, p) {
        // 左边界两个顶点
        if ((node->pos.x == minx) && (node->pos.y == miny || node->pos.y == maxb)) {
            if (node->cnt != 1) {
                return false;
            }
        // 右边界两个顶点
        } else if ((node->pos.x == maxa) && (node->pos.y == miny || node->pos.y == maxb)) {
            if (node->cnt != 1) {
                return false;
            }
        // 内部顶点
        } else {
            if (node->cnt % 2) {
                return false;
            }
        }
    }

    /* 释放hash表 */
    HASH_ITER(hh, root, node, p) {
        HASH_DEL(root, node);
        free(node);
    }

    return true;
}