Всем привет! Долго пытаюсь решить задачу, не вижу никаких логических ошибок(плохо знаком с JAVA и,может быть, ошибка в реализации). Тот, кто решил, подскажите, в чём проблема.

Решаю так: беру n-ю точку, произвожу инверсию относительно n-й точки (R=1). Затем ищу прямую, делящую плоскость на 2 части, чтобы в каждой части было ровно  (N-3)/2 точек (кроме n-й и 2х выбранных для прямой). Выбранные 3 точки и есть ответ.
Ищу прямую так (среди конечных точек): найдём самую нижнюю точку, сделаем её n-1 -й; она войдёт в ответ; перенесём СК в эту точку; затем отсортируем относительно неё (точки) оставшиеся точки и выберем из них среднюю.
Почему алгоритм корректен? После инверсии имеем n-1 конечные точки и 1 бесконечную. Заметим, что нет прямой, проходящей через 3 конечные точки (если такая есть, то возможны 2 варианта: 1)прямая проходит через О - тогда при обратной инверсии она проходит через О и при этом содержит 4 точки; 2)прямая не проходит через О - тогда при обратной инверсии она перейдёт в окружность, проходящую через О, тогда эти 3 точки и бесконечная точка лежат на одной окружности). А тогда можно найти прямую, разделяющую плоскость на 2 части, в каждой из которых содержится равное число конечных точек. Одна часть полуплоскости перейдёт во внутреннюю часть окружности, другая - во внешнюю.


import java.math.*;
import java.util.*;

public class BigNumbers
{
   final int nmax=5005;

   public static BigInteger Px[], Py[], z[];
   public static int n;

   public static boolean Equal(BigInteger x1, BigInteger y1, BigInteger z1, BigInteger x2, BigInteger y2, BigInteger z2)
   {
      BigInteger A = (x1.multiply(z2)).subtract(x2.multiply(z1));
      BigInteger B = (y1.multiply(z2)).subtract(y2.multiply(z1));
      return (A.compareTo(BigInteger.ZERO)==0 && B.compareTo(BigInteger.ZERO)==0);
   }

   public static boolean Less(BigInteger x1, BigInteger y1, BigInteger z1, BigInteger x2, BigInteger y2, BigInteger z2)   //полярный угол строго меньше
   {
         if(Equal(x1,y1,z1,x2,y2,z2)) return false;

         if(y1.compareTo(BigInteger.ZERO)==0) return x1.compareTo(BigInteger.ZERO)==1;
         else
         {
            if(x1.compareTo(BigInteger.ZERO)==1)
            {
               if(x2.compareTo(BigInteger.ZERO)!=1) return true;
               BigInteger v=(y2.multiply(x1)).subtract(x2.multiply(y1));
               return v.compareTo(BigInteger.ZERO)==1;
            }
            else
            {
               if(x1.compareTo(BigInteger.ZERO)==0) return x2.compareTo(BigInteger.ZERO)==-1;
               else
               {
                  BigInteger v=(y2.multiply(x1)).subtract(x2.multiply(y1));
                  return (x2.compareTo(BigInteger.ZERO)==-1 && v.compareTo(BigInteger.ZERO)==1);
               }
            }
         }
   }

   public static boolean More(BigInteger x1, BigInteger y1, BigInteger z1, BigInteger x2, BigInteger y2, BigInteger z2)  //полярный угол строго больше
   {
         return Less(x2,y2,z2,x1,y1,z1);
   }

   public static void QSort(int L, int R)
   {
      int m=(L+R)/2;
      int i=L;
      int j=R;

      while(i<=j)
      {
         BigInteger xi,yi,zi,xj,yj,zj,xm,ym,zm;

         xm=(Px[m].multiply(z[n-1])).subtract(z[m].multiply(Px[n-1]));  //здесь перемещаем СК относительно n-1 - й точки
         ym=(Py[m].multiply(z[n-1])).subtract(z[m].multiply(Py[n-1]));
         zm=z[m].multiply(z[n-1]);

         xi=(Px[i].multiply(z[n-1])).subtract(z[i].multiply(Px[n-1]));
         yi=(Py[i].multiply(z[n-1])).subtract(z[i].multiply(Py[n-1]));
         zi=z[i].multiply(z[n-1]);

         while(Less(xi,yi,zi,xm,ym,zm))
         {
            i++;
            if(i<=n)
            {
               xi=(Px[i].multiply(z[n-1])).subtract(z[i].multiply(Px[n-1]));
               yi=(Py[i].multiply(z[n-1])).subtract(z[i].multiply(Py[n-1]));
               zi=z[i].multiply(z[n-1]);
            }
         }

         xj=(Px[j].multiply(z[n-1])).subtract(z[j].multiply(Px[n-1]));
         yj=(Py[j].multiply(z[n-1])).subtract(z[j].multiply(Py[n-1]));
         zj=z[j].multiply(z[n-1]);
         while(More(xj,yj,zj,xm,ym,zm))
         {
            j--;
            if(j>=1)
            {
               xj=(Px[j].multiply(z[n-1])).subtract(z[j].multiply(Px[n-1]));
               yj=(Py[j].multiply(z[n-1])).subtract(z[j].multiply(Py[n-1]));
               zj=z[j].multiply(z[n-1]);
            }
         }

         if(i<=j)
         {
            BigInteger v;
            v=Px[i]; Px[i]=Px[j]; Px[j]=v;
            v=Py[i]; Py[i]=Py[j]; Py[j]=v;
            v=z[i]; z[i]=z[j]; z[j]=v;
            i++;
            j--;
         }
      }
      if(L<j) QSort(L, j);
      if(i<R) QSort(i, R);
   }


   public static void main(String args[])
   {
      Scanner sc=new Scanner(System.in);

      n=sc.nextInt();

      Px=new BigInteger[n+1];
      Py=new BigInteger[n+1];
      z=new BigInteger[n+1];

      for(int i=1;i<=n;i++)
      {
         Long x, y;
         x=sc.nextLong();
         y=sc.nextLong();
         Px[i]=BigInteger.valueOf(x);
         Py[i]=BigInteger.valueOf(y);
      }

      for(int i=1;i<=n-1;i++)        //относительно n-й точки производим инверсию
      {
         Px[i]=Px[i].subtract(Px[n]);
         Py[i]=Py[i].subtract(Py[n]);
         z[i]=(Px[i].multiply(Px[i])).add(Py[i].multiply(Py[i])); //теперь все координаты(кроме n точки) имеют вид ((xi-xn)/zi, (yi-yn)/zi)
      }

      for(int i=1;i<=n-2;i++)   //ищем самую нижнюю точку-она должна стать n-1 - й
      {
         BigInteger v1=z[n-1].multiply(Py[i]);
         BigInteger v2=z[i].multiply(Py[n-1]);
         if(v1.compareTo(v2)==-1)
         {
            BigInteger v;
            v=Px[i]; Px[i]=Px[n-1]; Px[n-1]=v;
            v=Py[i]; Py[i]=Py[n-1]; Py[n-1]=v;
            v=z[i]; z[i]=z[n-1]; z[n-1]=v;
         }
      }

      QSort(1,n-2);//сортируем по полярному углу от 0 до Pi

      Px[n-1]=Px[n-1].add(Px[n]);   //получаем начальные коорд.
      Py[n-1]=Py[n-1].add(Py[n]);

      int m = (n-1)/2;
      Px[m]=Px[m].add(Px[n]);
      Py[m]=Py[m].add(Py[n]);

      System.out.println(Px[n-1]+" "+Py[n-1]);
      System.out.println(Px[m]+" "+Py[m]);
      System.out.print(Px[n]+" "+Py[n]);
   }
}

Edited by author 27.01.2018 13:53