NC24853. [USACO 2009 Nov B]Claustrophobic Cows
描述
By way of example, consider this field of cows (presented on a typewriter grid that has slightly different proportions than you might expect): 10 | . . . . . . . 3 . . . . . 9 | . 1 . . 2 . . . . . . . . 8 | . . . . . . . . . . . . . 7 | . . . . . . . . . . 4 . . 6 | . . . . . . 9 . . . . . . 5 | . 8 . . . . . . . . . . . 4 | . . . . . 7 . . . . . . . 3 | . . . . . . . . . 5 . . . 2 | . . . . . . . . . . . . . 1 | . . . . 6 . . . . . . . . 0 --------------------------- 1 1 1 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 Quick visual inspection shows that cows 7 and 9 are closest together (the distance separating them is sqrt(1*1+2*2) = sqrt(5), so the output would be '7 9' on a single line (without quotes, of course).
输入描述
* Line 1: A single integer: N
* Lines 2..N+1: Line i contains the coordinates of cow i expressed as two space-separated integers: Xi and Yi
输出描述
* Line 1: The two numerical IDs of the closest pair of cows (sorted)
示例1
输入:
9 2 9 5 9 8 10 11 7 10 3 5 1 6 4 2 5 7 6
输出:
7 9
pypy3(pypy3.6.1) 解法, 执行用时: 248ms, 内存消耗: 22768K, 提交时间: 2021-05-03 21:47:20
n = int(input())
x = []
y = []
for i in range(0, n) :
a, b = map(int,input().split())
x.append(a), y.append(b)
dis = 10000000000
ans_1 = 0
ans_2 = 0
for i in range(0, n) :
for j in range(0, i) :
temp=((x[i] - x[j])**2 + (y[i] - y[j])**2) **0.5
if temp < dis :
ans_1 = j
ans_2 = i
dis = temp
print(ans_1 + 1, ans_2 + 1)
C++11(clang++ 3.9) 解法, 执行用时: 9ms, 内存消耗: 508K, 提交时间: 2020-02-17 19:48:53
#include<iostream>
using namespace std;
int a[2048],b[2048];
int main()
{
long long n,i,j,mn=0x3f3f3f3f,k1=1,k2=2,t1,t2;
cin>>n;
for(i=1;i<=n;++i)
cin>>a[i]>>b[i];
for(i=1;i<n;++i)
for(j=i+1;j<=n;++j)
{
t1=(a[i]-a[j])*(a[i]-a[j]);
t2=(b[i]-b[j])*(b[i]-b[j]);
if(t1+t2<mn)
mn=t1+t2,k1=i,k2=j;
}
cout<<k1<<" "<<k2<<endl;
return 0;
}
Pascal(fpc 3.0.2) 解法, 执行用时: 12ms, 内存消耗: 256K, 提交时间: 2019-08-25 10:16:35
var
x,y:array[1..2000] of longint;
n,i,j,xx,yy,z:longint;
begin
read(n);
z:=2100000000;
for i:=1 to n do
begin
read(x[i],y[i]);
for j:=1 to i-1 do
if sqr(abs(x[i]-x[j]))+sqr(abs(y[i]-y[j]))<z then
begin
z:=sqr(abs(x[i]-x[j]))+sqr(abs(y[i]-y[j]));
xx:=j;
yy:=i;
end;
end;
writeln(xx,' ',yy);
end.