分治法 c语言代码 某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个有n口油井的油田。从每口油井都要有一条输油管道沿最短路经(或南或北)与主管道相连。如果给定n口油井的位置，即它们的x坐标（东西向）和y坐标（南北向），应如何确定主管道的最优位置，使各油井到主管道之间的输油管道长度总和最小的位置?可在线性时间内确定主管道的最优位置。 给定n口油井的位置，编程计算各油井到主管道之间的输油管道最小长度总和。 输入格式： 输入的第1行是油井数n，1<=n<=10000。接下来n行是油井的位置，每行2个用空格割开的整数x和y，-10000<=x，y<=10000。

以下是使用分治法求解的C语言代码：

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

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

// 按照油井的x坐标排序
int cmp(const void *a, const void *b) {
    oilfield *oa = (oilfield *)a;
    oilfield *ob = (oilfield *)b;
    return oa->x - ob->x;
}

// 求解油井之间的输油管道长度总和
double pipeline_length(oilfield a[], int left, int right, int mid, double d) {
    double sum = 0;
    for (int i = left; i <= right; i++) {
        double dx = a[i].x - a[mid].x;
        double dy = a[i].y - a[mid].y;
        sum += sqrt(dx * dx + dy * dy);
    }
    return sum + d;
}

// 分治求解主管道的最优位置
double find_pipe(oilfield a[], int left, int right) {
    if (left == right) {
        return a[left].y;
    } else if (left + 1 == right) {
        return (a[left].y + a[right].y) / 2.0;
    } else {
        int mid = (left + right) / 2;
        double y_left = find_pipe(a, left, mid);
        double y_right = find_pipe(a, mid + 1, right);
        double d = fmin(pipeline_length(a, left, mid, mid, 0), pipeline_length(a, mid + 1, right, mid, 0));
        double y_mid = a[mid].y;
        for (int i = mid - 1; i >= left && (a[mid].x - a[i].x) < d; i--) {
            double length = pipeline_length(a, i, mid, mid, d);
            if (length < pipeline_length(a, i, mid, mid, 0)) {
                d = length;
                y_mid = a[i].y;
            }
        }
        for (int i = mid + 1; i <= right && (a[i].x - a[mid].x) < d; i++) {
            double length = pipeline_length(a, mid + 1, i, mid, d);
            if (length < pipeline_length(a, mid + 1, i, mid, 0)) {
                d = length;
                y_mid = a[i].y;
            }
        }
        return (y_left + y_right + y_mid) / 3.0;
    }
}

int main() {
    int n;
    scanf("%d", &n);
    oilfield a[n];
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &a[i].x, &a[i].y);
    }
    qsort(a, n, sizeof(oilfield), cmp);
    double y = find_pipe(a, 0, n - 1);
    printf("%.2f\n", y);
    return 0;
}

代码中首先定义了一个结构体oilfield来存储油井的位置信息。在主函数中，先读入油井的位置信息，并按照x坐标排序。

接着，通过递归调用find_pipe函数来分治求解主管道的最优位置。在该函数中，分别计算左半部分和右半部分的最优位置，然后求它们的平均值作为主管道的位置。同时，还需要计算跨越左右两部分的主管道的位置。

具体来说，首先计算跨越中间位置mid的最短主管道长度d，即pipeline_length(a, left, mid, mid, 0)和pipeline_length(a, mid + 1, right, mid, 0)中的最小值。然后，在以mid为中心、左右两端分别到mid为半径的圆内搜索主管道的位置。使用pipeline_length函数来计算油井之间的输油管道长度总和，使用fmin函数来更新最短主管道长度d和对应的主管道位置y_mid。

最后，返回左半部分、右半部分和跨越中间位置mid的主管道位置的平均值。在计算平均值时，使用了三分法来平衡左右两部分和跨越中间位置mid的重要性。