ZJUTOJ-1502-KK看了新闻

发表于 | 分类于 | 阅读次数

关于数学坐标系中距离计算的题目。

Description

KK 最近看新闻，看到某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个有 n 口油井的油田。从每口油井都要有一条输油管道沿最短路经(或南或北)与主管道相连。如果给定 n 口油井的位置,即它们的 x 坐标（东西向）和 y 坐标（南北向）,应如何确定主管道的最优位置,即使各油井到主管道之间的输油管道长度总和最小的位置? KK 想，这不就是给定 n 口油井的位置,编程计算各油井到主管道之间的输油管道最小长度总和嘛。

Input:

输入由多组测试数据组成。每组测试数据输入的第 1 行是油井数 n ，1≤n≤10000 。接下来 n 行是油井的位置，每行2个整数 x 和 y，-10000≤x，y≤10000。

Output:

对应每组输入，输出的第 1 行中的数是油井到主管道之间的输油管道最小长度总和。

Sample Input:

1
2
3
4
5
6
5
1 2
2 2
1 3
3 -2
3 3

Sample Output:

1
6

Solve:

根本没用到 x 坐标，仅仅使用 y 坐标求最小和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
#include <math.h>
using namespace std;
#define MAX_NUM 2048
int main() {
    int n;
    while(cin >> n) {
        int well[n][2];
        for(int i = 0; i < n; i++) 
        {
            cin >> well[i][0] >> well[i][1];
        }
        int minSum = MAX_NUM;
        for(int i = 0; i < n; i++) 
        {
            int tubeY = well[i][1];
            int sum = 0;
            for(int j = 0; j < n; j++) 
            {
                int distance = 0;
                if(tubeY == well[j][1]) 
                {
                    distance = 0;
                } else if(tubeY > well[j][1]) 
                {
                    distance = tubeY - well[j][1];
                } else 
                {
                    distance = well[j][1] - tubeY;
                }
                sum += distance;
            }
            minSum = min(sum, minSum);
        }
        cout << minSum;
    }
    return 0;
}

0%