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

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

How to solve this problem without long arithmetic?
Послано Felix_Mate 10 авг 2017 16:38
If i use double -> big error
If i use long long -> overflow
now i got Runtime error on java. Where I am wrong? I think my function Less is bad but I can't find mistake.

My code:
import java.math.*;
import java.util.*;

public class BigNumbers
{
   final int tmax=100;
   MathContext mc = new MathContext(tmax);

   final int nmax=5005;

   static int Pox[], Poy[], id[];
   static BigDecimal Px[], Py[];
   static int n, left;

   public static boolean Less(BigDecimal x1, BigDecimal y1, BigDecimal x2, BigDecimal y2)
   {
      return (y1.compareTo(BigDecimal.ZERO)!=-1) && (y2.compareTo(BigDecimal.ZERO)==1) &&
             ((y1.multiply(x2)).compareTo(x1.multiply(y2))==-1) ||
             (y1.compareTo(BigDecimal.ZERO)==-1) && ((y2.compareTo(BigDecimal.ZERO)!=-1)) ||
             ((x1.multiply(y2)).compareTo(x2.multiply(y1))==1);
   }

   public static BigDecimal modul2(BigDecimal x, BigDecimal y)
   {
         return (x.multiply(x)).add(y.multiply(y));
   }

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

      while(i<=j)
      {
         while(Less(Px[i],Py[i],Px[m],Py[m])) i++;
         while(!Less(Px[j],Py[j],Px[m],Py[m]) && j!=m) j--;
         if(i<=j)
         {
            BigDecimal Y=Px[i];
            Px[i]=Px[j];
            Px[j]=Y;
            Y=Py[i];
            Py[i]=Py[j];
            Py[j]=Y;
            int y=id[i];
            id[i]=id[j];
            id[j]=y;
            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();

      Pox=new int[n+1];
      Poy=new int[n+1];
      id=new int[n+1];
      Px=new BigDecimal[n+1];
      Py=new BigDecimal[n+1];

      for(int i=1;i<=n;i++)
      {
         int x, y;
         x=sc.nextInt();
         y=sc.nextInt();
         Pox[i]=x;
         Poy[i]=y;
      }

      System.out.println(Pox[1]+" "+Poy[1]);

      for(int i=1;i<=n-1;i++)
      {
         BigDecimal x=BigDecimal.valueOf(Pox[i+1]-Pox[1]);
         BigDecimal y=BigDecimal.valueOf(Poy[i+1]-Poy[1]);
         Px[i]=x.divide(modul2(x,y));
         Py[i]=y.divide(modul2(x,y));
         id[i]=i+1;
      }

      left=1;
      for(int i=2;i<=n-1;i++)
         if(Px[left].compareTo(Px[i])==1 || Px[left].compareTo(Px[i])==0 &&
            Py[left].compareTo(Py[i])==1) left=i;

      System.out.println(Pox[id[left]]+" "+Poy[id[left]]);

      for(int i=1;i<=n-1;i++)
      {
         Px[i]=Px[i].subtract(Px[left]);
         Py[i]=Py[i].subtract(Py[left]);
      }

      for(int i=left;i<=n-2;i++)
      {
         Px[i]=Px[i+1];
         Py[i]=Py[i+1];
      }

      QSort(1,n-2);
      System.out.print(Pox[id[(n-1)/2]]+" "+Poy[id[(n-1)/2]]);
   }
}