【华为OD机试2023】服务中心选址 100% C++ Java Python

题目描述

某公司要在某个城市开设服务中心，为了方便客户，服务中心需要尽可能地靠近客户。现在给出客户的坐标和服务中心的候选坐标，请你编写一个程序，找出最佳的服务中心位置。

输入格式

第一行包含一个整数 n，表示客户的数量。

接下来 n 行，每行包含两个整数 xi 和 yi，表示客户的坐标。

接下来一行包含一个整数 m，表示服务中心的候选坐标数量。

接下来 m 行，每行包含两个整数 xi 和 yi，表示服务中心的候选坐标。

输出格式

输出最佳的服务中心位置，保留两位小数。

数据范围

1≤n≤1000
1≤m≤1000
?10000≤xiyi≤10000

样例

输入样例：
4
-1 1
1 1
1 -1
-1 -1
4
0 0
0 1
1 0
1 1
输出样例：
0.00 0.00

C++ 代码

#include
#include
#include
#include
#include

using namespace std;

const int N = 1010;

int n m;
int x[N] y[N] xx[N] yy[N];

double get_dist(int a int b)
{
return sqrt((x[a] - xx[b]) * (x[a] - xx[b]) + (y[a] - yy[b]) * (y[a] - yy[b]));
}

int main()
{
scanf(%d &n);
for (int i = 0; i < n; i ++ ) scanf(%d%d &x[i] &y[i]);
scanf(%d &m);
for (int i = 0; i < m; i ++ ) scanf(%d%d &xx[i] &yy[i]);

double res = 1e20;
int idx = -1;
for (int i = 0; i < m; i ++ )
{
double sum = 0;
for (int j = 0; j < n; j ++ ) sum += get_dist(j i);
if (sum < res)
{
res = sum;
idx = i;
}
}

printf(%.2lf %.2lf
xx[idx] * 1.0 yy[idx] * 1.0);

return 0;
}

Java 代码

import java.util.Scanner;

public class Main
{
static int n m;
static int[] x = new int[1010] y = new int[1010] xx = new int[1010] yy = new int[1010];

public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
for (int i = 0; i < n; i ++ )
{
x[i] = scan.nextInt();
y[i] = scan.nextInt();
}
m = scan.nextInt();
for (int i = 0; i < m; i ++ )
{
xx[i] = scan.nextInt();
yy[i] = scan.nextInt();
}

double res = 1e20;
int idx = -1;
for (int i = 0; i < m; i ++ )
{
double sum = 0;
for (int j = 0; j < n; j ++ ) sum += get_dist(j i);
if (sum < res)
{
res = sum;
idx = i;
}
}

System.out.printf(%.2f %.2f
xx[idx] * 1.0 yy[idx] * 1.0);
}

static double get_dist(int a int b)
{
return Math.sqrt((x[a] - xx[b]) * (x[a] - xx[b]) + (y[a] - yy[b]) * (y[a] - yy[b]));
}
}

Python 代码

n = int(input())
x = [0] * n
y = [0] * n
for i in range(n):
x[i] y[i] = map(int input().split())

m = int(input())
xx = [0] * m
yy = [0] * m
for i in range(m):
xx[i] yy[i] = map(int input().split())

res = 1e20
idx = -1
for i in range(m):
sum = 0
for j in range(n):
sum += ((x[j] - xx[i]) ** 2 + (y[j] - yy[i]) ** 2) ** 0.5
if sum < res:
res = sum
idx = i

print(%.2f %.2f % (xx[idx] yy[idx]))