某石油公司有n口油井,为方便输送石油,计划修建输油管道。根据设计要求,水平方向有一条主管道,每口油井修一条垂直方向的支线管道通向主管道。请设计一种算法确定主管道的位置,使得所有油井到主管道之间的支线管道长度的总和最小。
输入格式:
每个输入文件为一个测试用例,每个文件的第一行给出一个正整数n(1≤n≤1000000),表示油井数量,从第二行起的n行数据,表示每口油井的位置,每行包含以空格分隔的两个整数,分别表示每口油井的横坐标x(−10000≤x≤10000)和纵坐标y(−10000≤y≤10000)。
下面是我的代码:pta老是提示段错误 救助
#include<stdio.h>
#include<stdlib.h>
int inc(const void *a, const void *b)
{
return *(int *)a - *(int *)b;
}
int main ()
{
int i,n,x;
int y[100000];
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d %d",&x,&y[i]);
qsort(y, n, sizeof(int), inc);
int middle=0;
if(n%2==0){
middle=n/2;
}
else{
middle=(n-1)/2;
}
unsigned long long sum=0;
for(i=0;i<n;i++)
{
sum+=abs(y[i]-y[middle]);
}
printf("%llu",sum);
}