ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1103. Карандаши и окружности

where i wrong?
Послано Felix_Mate 21 дек 2017 15:19
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]));
         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++)
      {
         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]));
      }

      for(int i=1;i<=n-2;i++)
      {
         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);

      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]);
   }
}