根据四点坐标用C语言求水平方向上最大矩形四点坐标

可以使用暴力枚举法或者扫描线算法来解决这个问题。下面分别介绍这两种算法：

1. 暴力枚举法

首先需要明确，最大矩形一定是由某两个点确定的，因此我们可以使用两重循环枚举所有可能的点对，并计算它们组成的矩形的面积。最后得到面积最大的矩形即可。

具体实现可以按照以下步骤进行：

1. 使用两重循环枚举所有可能的点对，设当前点对为 (i, j) 和 (k, l)。
2. 判断这两个点是否在同一水平线上，如果不在同一水平线上，则无法构成矩形，跳过本次循环。
3. 计算以这两个点为对角线的矩形的面积，如果该面积比之前的最大面积还大，则更新最大面积和最大矩形的四个顶点坐标。
4. 循环结束后，输出最大矩形的四个顶点坐标。

代码示例：

#include <stdio.h>

typedef struct {
    int x, y;
} Point;

int main() {
    Point points[4];
    int max_area = 0;
    Point max_rect[4];

    // 输入四个点的坐标
    for (int i = 0; i < 4; i++) {
        scanf("%d%d", &points[i].x, &points[i].y);
    }

    // 枚举所有点对
    for (int i = 0; i < 4; i++) {
        for (int j = i + 1; j < 4; j++) {
            // 判断是否在同一水平线上
            if (points[i].y == points[j].y) {
                continue;
            }
            for (int k = 0; k < 4; k++) {
                if (k == i || k == j) {
                    continue;
                }
                for (int l = k + 1; l < 4; l++) {
                    if (l == i || l == j) {
                        continue;
                    }

                    // 判断是否在同一水平线上
                    if (points[k].y == points[l].y) {
                        continue;
                    }

                    // 计算矩形面积
                    int area = abs(points[i].x - points[j].x) * abs(points[k].y - points[l].y);
                    if (area > max_area) {
                        max_area = area;
                        max_rect[0] = points[i];
                        max_rect[1] = points[j];
                        max_rect[2] = points[k];
                        max_rect[3] = points[l];
                    }
                }
            }
        }
    }

    // 输出最大矩形的四个顶点坐标
    for (int i = 0; i < 4; i++) {
        printf("(%d, %d)\n", max_rect[i].x, max_rect[i].y);
    }

    return 0;
}

2. 扫描线算法

扫描线算法是一种优化的算法，它可以在 O(nlogn) 的时间复杂度内解决这个问题。具体思路如下：

1. 将所有点按照 x 坐标从小到大排序。
2. 从左往右扫描所有点，维护一个高度为当前扫描线的最小 y 坐标的矩形集合。这个集合可以使用平衡树来维护，时间复杂度为 O(logn)。
3. 当扫描到一个点时，将它添加到矩形集合中，然后计算该集合中最大的矩形，更新最大面积和最大矩形的四个顶点坐标。
4. 扫描结束后，输出最大矩形的四个顶点坐标。

代码示例：

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int x, y;
} Point;

typedef struct {
    int x1, y1, x2, y2;
} Rectangle;

// 比较两个 Point 的 x 坐标大小
int cmp(const void* p1, const void* p2) {
    Point* a = (Point*) p1;
    Point* b = (Point*) p2;
    return a->x - b->x;
}

// 比较两个 Rectangle 的面积大小
int cmp_rect(const void* p1, const void* p2) {
    Rectangle* a = (Rectangle*) p1;
    Rectangle* b = (Rectangle*) p2;
    return (a->x2 - a->x1) * (a->y2 - a->y1) - (b->x2 - b->x1) * (b->y2 - b->y1);
}

int main() {
    Point points[4];
    Rectangle rects[4];
    int max_area = 0;
    Point max_rect[4];

    // 输入四个点的坐标
    for (int i = 0; i < 4; i++) {
        scanf("%d%d", &points[i].x, &points[i].y);
    }

    // 将所有点按照 x 坐标排序
    qsort(points, 4, sizeof(Point), cmp);

    // 扫描所有点
    int j = 0;
    for (int i = 0; i < 4; i++) {
        // 将当前点添加到矩形集合中
        rects[j].x1 = rects[j].x2 = points[i].x;
        rects[j].y1 = rects[j].y2 = points[i].y;
        j++;

        // 将当前矩形集合按照 y 坐标从小到大排序
        qsort(rects, j, sizeof(Rectangle), cmp_rect);

        // 计算最大矩形
        for (int k = 0; k < j; k++) {
            int area = (rects[k].x2 - rects[k].x1) * (points[i].y - rects[k].y1);
            if (area > max_area) {
                max_area = area;
                max_rect[0].x = rects[k].x1;
                max_rect[0].y = rects[k].y1;
                max_rect[1].x = rects[k].x2;
                max_rect[1].y = rects[k].y1;
                max_rect[2].x = rects[k].x1;
                max_rect[2].y = points[i].y;
                max_rect[3].x = rects[k].x2;
                max_rect[3].y = points[i].y;
            }
            if (rects[k].y2 > points[i].y) {
                rects[k].y2 = points[i].y;
            }
            if (rects[k].y1 >= rects[k].y2) {
                j--;
                for (int l = k; l < j; l++) {
                    rects[l] = rects[l + 1];
                }
                k--;
            }
        }
    }

    // 输出最大矩形的四个顶点坐标
    for (int i = 0; i < 4; i++) {
        printf("(%d, %d)\n", max_rect[i].x, max_rect[i].y);
    }

    return 0;
}