Welcome   HUNAN NORMAL UNIVERSITY ACM/ICPC Judge Online
Home
FAQs
Problem Set
Practices
Online Contests
Major Exercises
OI Special
Judgement
Submit
Online Status
User Ranklist
Users
Register new
Login
Web Links
Hunan Normal University
College of Information Science and Engineering
输油管道问题
Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB
Total submit users: 28, Accepted users: 27
Problem 11096 : No special judgement
Problem description
  某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个有n 口油井的油田。从每口油井都要有一条输油管道沿最短路经(或南或北)与主管道相连。如果给定n口油井的位置,即它们的x 坐标(东西向)和y 坐标(南北向),应如何确定主管道的最优位置,即使各油井到主管道之间的输油管道长度总和最小的位置? 给定n 口油井的位置,编程计算各油井到主管道之间的输油管道最小长度总和。

Input
  第1 行是油井数n,1<=n<=10000。接下来n 行是油井的位置,每行2个整数x和y,-10000<=x,y<=10000。

Output
  油井到主管道之间的输油管道最小长度总和。

Sample Input
5
1 2
2 2
1 3
3 -2
3 3
Sample Output
6
Submit   Clarifications   Judge Status  Problems  Ranklist 

HUNAN NORMAL UNIVERSITY ACM/ICPC Judge Online, Version 2010.5.5.final.
Web visits:2042 today,12073091 total, since 2010-05-07