Как найти среди N точек с целочисленными координатами пару самых ближних и пару самых дальних друг от друга точек?

Данные задачи

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

Входные данные

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

Выходные данные

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

Мое решение прошло 10 тестов из 20:

package task1123;

import java.util.Scanner;
import java.util.Locale;

public class Task1123 {
    public static class point {
        public int x;
        public int y;
        
        public point(int x, int y) {
            this.x = x;
            this.y = y;

        }
    }

    public static double dist(point a,point b) {
        return Math.sqrt((a.x - b.x)*(a.x - b.x)+(a.y - b.y)*(a.y - b.y));
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        sc.useLocale(Locale.US);
        point a[] = new point[1000];
        int n, p = 0, q = 1, r = 0,s = 1;
        double c = 0, mn, mx;
        n = sc.nextInt();
        for(int i = 0; i < n; i++)
        {
            a[i] = new point(sc.nextInt(), sc.nextInt());
        }
        mn = dist(a[0],a[1]);
        mx = mn;
        for(int i = 0;i < n - 1; i++)
        {
            for(int j = i + 1; j < n; j++)
            {
                c = dist(a[i],a[j]);
                if(c < mn){
                    mn=c;
                    p=i;
                    q=j;
                }
                else if(c > mx){
                    mx=c;
                    r=i;
                    s=j;
                }
            }
        }
        System.out.println((p + 1) + " " + (q + 1));
        System.out.println((r + 1) + " " + (s + 1));
    }
}