pipe.cpp

某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个有n 口油井的油田。从每口油井都要有一条输油管道沿最短路经(或南或北)与主管道相连。如果给定n 口油井的位置,即它们的x 坐标（东西向）和y

#include<fstream.h>
int main()
{
	   ifstream in("input.txt");
	   ofstream out("output.txt");

	   int s;
	   in>>s;

       int a[20001];
	   int min=20000;
	   int max=0;

	   for (int i=0; i<20001; i++)   a[i] = 0;	  

       //输入
	   int y;
	   if (s<100)
	   {
		    for (i=0; i<s; i++)
			{
				in>>y>>y;
				y+=10000;
				a[y]++;
				if (y<min) min=y;
			    if (y>max) max=y;
			}
	   }
	   else
	   {
		    min = 0;
		    max = 20000;
		    for (i=0; i<s; i++)
			{
				in>>y>>y;
				y+=10000;
				a[y]++;			    
			}
	   }


	   //取中位数
	   long count=0;
	   int z = 0;
	   int mids = s/2;
	   for (i=min; i<=max; i++)
	   {
		   if (a[i]>0)   count+=a[i];
		   if (count>mids)
		   {
			   z = i;
			   break;
		   }
	   }


	   //计算最短距离
	   long result=0;
	   for (i=min; i<z; i++)
	   {
		   if (a[i]>0)  result += (z-i)*a[i];
	   }
	   for (i=z; i<=max; i++)
	   {
		   if (a[i]>0)  result += (i-z)*a[i];
	   }

	   out<<result;

       return 0;
}