运用蛮力法的基本思想解决凸包问题、最近对问题C语言

凸包问题是指给定平面上的一组点，求出能包含所有这些点的最小凸多边形的问题。蛮力法是一种朴素的解法，其基本思想是枚举所有可能的凸多边形并判断是否符合要求，最终得到最小凸多边形。

下面是一个用蛮力法解决凸包问题的C语言代码示例：

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

typedef struct{
    int x;
    int y;
} Point;

int ccw(Point a, Point b, Point c){
    int area = (b.x-a.x)*(c.y-a.y) - (c.x-a.x)*(b.y-a.y);
    if(area > 0) return 1;     // 逆时针
    else if(area < 0) return -1;   // 顺时针
    else return 0;     // 平行
}

int cmp(const void* p1, const void* p2){
    Point* a = (Point*)p1;
    Point* b = (Point*)p2;
    if(a->x != b->x)
        return a->x - b->x;
    else
        return a->y - b->y;
}

void convex_hull(Point* points, int n){
    qsort(points, n, sizeof(Point), cmp);
    Point* hull = (Point*)malloc(sizeof(Point) * n);
    int idx = 0, start = 0;
    for(int i=0; i<n; i++){
        while(idx-start >= 2 && ccw(hull[idx-2], hull[idx-1], points[i]) <= 0) idx--;
        hull[idx++] = points[i];
    }
    start = --idx;
    for(int i=n-2; i>=0; i--){
        while(idx-start >= 2 && ccw(hull[idx-2], hull[idx-1], points[i]) <= 0) idx--;
        hull[idx++] = points[i];
    }
    printf("Convex Hull:\n");
    for(int i=0; i<idx-1; i++){
        printf("(%d, %d), ", hull[i].x, hull[i].y);
    }
    printf("(%d, %d)\n", hull[idx-1].x, hull[idx-1].y);
    free(hull);
}

int main(){
    Point points[] = {{0,0}, {0,1}, {1,0}, {1,1}, {0.5, 0.5}};
    int n = sizeof(points) / sizeof(Point);
    convex_hull(points, n);
    return 0;
}

该代码中，我们先对点集按照x坐标进行排序，然后逐个加入到凸包中，如果加入新点后不再是凸多边形，则将凸包的最后一个点删除，直到满足要求为止。最后，再从后往前遍历一遍点集，将多余的点删除。

最近对问题是指给定平面上的一组点，求出距离最近的两个点之间的距离。下面是一个用蛮力法解决最近对问题的C语言代码示例：

#include <stdio.h>
#include <math.h>

typedef struct{
    double x;
    double y;
} Point;

double dist(Point a, Point b){
    return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
}

double closest_pair(Point* points, int n){
    double min_dist = 1e9;
    for(int i=0; i<n; i++){
        for(int j=i+1; j<n; j++){
            double d = dist(points[i], points[j]);
            if(d < min_dist) min_dist = d;
        }
    }
    return min_dist;
}

int main(){
    Point points[] = {{0,0}, {0,1}, {1,0}, {1,1}, {0.5, 0.5}};
    int n = sizeof(points) / sizeof(Point);
    double min_dist = closest_pair(points, n);
    printf("Closest Pair: %lf\n", min_dist);
    return 0;
}

该代码中，我们先枚举所有的点对，计算它们之间的距离，并更新最小距离。最后返回最小距离即可。由于蛮力法的时间复杂度为O(N^2)，因此该算法不适用于大规模的问题。针对最近对问题，还可以使用分治法或基于数据结构的算法进行优化。