Решение задачи №1223 «Точки на плоскости» с ACMP





Решение задачи №1223 «Точки на плоскости» с ACMP

Условие задачи

На плоскости заданы N точек с целочисленными координатами. Требуется найти среди них пару самых ближних и пару самых дальних друг от друга точек.

Входные данные
Первая строка входного файла INPUT.TXT содержит целое число N (2 ≤ N ≤ 1000) – количество точек. Далее следует N строк пар целых чисел (Xi,Yi), описывающих координаты первой, второй и т.д. точек соответственно (-109 ≤ Xi,Yi ≤ 109).

Выходные данные
В первой строке выходного файла OUTPUT.TXT выведите через пробел номера пары ближних друг к другу точек. Во второй строке выведите номера пары дальних друг от друга точек. В случае неоднозначности определения ответа выведите любой.

#include<iostream>
#include<cmath>
using namespace std;
struct point { double x;double y;};
double d(point p1,point p2){
return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}
main(){
point a[1000];int n,i,j,p=0,q=1,r=0,s=1;double c,mn,mx;
cin>>n;
for(i=0;i<n;++i)cin>>a[i].x>>a[i].y;
mn=d(a[0],a[1]);
mx=mn;
for(i=0;i<n-1;++i)
for(j=i+1;j<n;++j){c=d(a[i],a[j]);
if(c<mn){mn=c;p=i;q=j;}
else if(c>mx){mx=c;r=i;s=j;}
}
cout<<p+1<<' '<<q+1<<endl<<r+1<<' '<<s+1;
}



Условия задач взяты с сайта acmp.ru