Обсуждение @ 1103. Карандаши и окружности @ Timus Online Judge

Parassat Kyzyrkanov WA#7 // Задача 1103. Карандаши и окружности 14 авг 2023 20:03

-XraY- Add new test, please. [2] // Задача 1103. Карандаши и окружности 28 мар 2013 01:06

Felix_Mate Помогите разобраться (кто решил)! // Задача 1103. Карандаши и окружности 27 янв 2018 13:49

Всем привет! Долго пытаюсь решить задачу, не вижу никаких логических ошибок(плохо знаком с 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

Felix_Mate where i wrong? // Задача 1103. Карандаши и окружности 21 дек 2017 15:19

Felix_Mate How to solve this problem without long arithmetic? // Задача 1103. Карандаши и окружности 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]]);
   }
}

-XraY- wrong tests! n >= 3! [2] // Задача 1103. Карандаши и окружности 23 окт 2011 23:37

Victor Barinov (TNU) My algo complexity is O(n^4), Is it exists any more efficient? (-) [5] // Задача 1103. Карандаши и окружности 11 май 2005 18:09

scorpiowf wa4 [1] // Задача 1103. Карандаши и окружности 1 июл 2009 08:45

Mamuka Sakhelashvili [Freeuni] WA 7 // Задача 1103. Карандаши и окружности 19 фев 2014 01:36

vietlong WA #2 // Задача 1103. Карандаши и окружности 11 авг 2011 23:21

Loky_Yuri [USTU] What algorithm should you use? Random and nothing more... [1] // Задача 1103. Карандаши и окружности 25 июн 2007 20:15

Sergey Baskakov, Raphail and Denis Can a square of an integer number be negative? [1] // Задача 1103. Карандаши и окружности 6 апр 2005 01:02

BFL Hints [1] // Задача 1103. Карандаши и окружности 13 ноя 2005 11:05

Zhang Chihao I got WA on test #7 [2] // Задача 1103. Карандаши и окружности 3 май 2006 21:53

Can someone help me?

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;

struct Tpoint{
    double x,y;
};

const double eps=1e-8;
const double inf=2147483647.0;

int n;
Tpoint p[6000];
int id[6000];

int dcmp(double x){
    return x<-eps?-1:x>eps;
}

double cross(Tpoint p0,Tpoint p1,Tpoint p2){
    double x1=p1.x-p0.x;
    double x2=p2.x-p0.x;
    double y1=p1.y-p0.y;
    double y2=p2.y-p0.y;
    return x1*y2-x2*y1;
}

double dot(Tpoint p0,Tpoint p1,Tpoint p2){
    double x1=p1.x-p0.x;
    double x2=p2.x-p0.x;
    double y1=p1.y-p0.y;
    double y2=p2.y-p0.y;
    return x1*x2+y1*y2;
}

double angle(Tpoint p0,Tpoint p1,Tpoint p2){
    double cr=cross(p0,p1,p2);
    double dt=dot(p0,p1,p2);
    if(!dcmp(cr)) cr=0.0;
    if(!dcmp(dt)) dt=0.0;
    return atan2(cr,dt);
}

bool cmp(const Tpoint& a,const Tpoint &b){
    return dcmp(atan2(a.y-p[0].y,a.x-p[0].x)-atan2(b.y-p[0].y,b.x-p[0].x))<0;
}

bool cmp2(const int &a,const int &b){
    return dcmp(angle(p[a],p[0],p[1])-angle(p[b],p[0],p[1]))<0;
}

void init(){
    Tpoint tp;
    int i,j;
    double minx,miny;
    cin>>n;
    for(i=0;i<n;i++) cin>>p[i].x>>p[i].y;
    for(minx=miny=inf,i=0;i<n;i++)
    if(dcmp(p[i].x-minx)<0 || (dcmp(p[i].x-minx)==0 && dcmp(p[i].y-miny)<0)){
        minx=p[i].x;
        miny=p[i].y;
        j=i;
    }
    tp=p[j];
    p[j]=p[0];
    p[0]=tp;
    sort(p+1,p+n,cmp);
}

void solve(){
    int i;
    for(i=0;i<n;i++) id[i]=i;
    sort(id+2,id+n,cmp2);
    cout<<p[0].x<<" "<<p[0].y<<endl;
    cout<<p[1].x<<" "<<p[1].y<<endl;
    //for(i=2;i<n;i++) cout<<p[id[i]].x<<" "<<p[id[i]].y<<" "<<angle(p[id[i]],p[0],p[1])<<endl;
    cout<<p[id[n/2+1]].x<<" "<<p[id[n/2+1]].y<<endl;
}

int main(){
    init();
    solve();
    return 0;
}

xiaomengxian Re: I got WA on test #7 [1] // Задача 1103. Карандаши и окружности 26 сен 2006 19:15

Me too....
BTW, are you from HNSDFZ?

gojiajunchao Re: I got WA on test #7 // Задача 1103. Карандаши и окружности 2 июн 2008 06:47

1e-8 => 1e-10 then you will AC

Razdolbay from SIS WA 12, need help. // Задача 1103. Карандаши и окружности 26 фев 2008 23:41

Anton Lun'ov WA3 // Задача 1103. Карандаши и окружности 7 янв 2008 04:38

Sandro (USU) Problem 1103 "Pensils and Circles" has been rejudged (+) [5] // Задача 1103. Карандаши и окружности 24 окт 2006 02:12

Some new tests were added.
52 authors with inexact calculations got WA.

Edited by author 24.10.2006 10:47

Sandro (USU) Re: Problem 1103 "Pensils and Circles" has been rejudged (+) // Задача 1103. Карандаши и окружности 3 апр 2007 13:54

There was an accuracy problem in the old validator. New validator uses long arithmetics. After rejudge some WA submits turned to AC, but authors with real (not integer) numbers in output now have WA.

Marko Bogdanovic Re: Problem 1103 "Pensils and Circles" has been rejudged (+) [3] // Задача 1103. Карандаши и окружности 10 апр 2007 01:50

It is ok that problem is rejudged, but it not ok to delete AC to authors which solution was previously accepted, because is server's fault, and this way we pay the damage.

svr Re: Problem 1103 "Pensils and Circles" has been rejudged (+) [2] // Задача 1103. Карандаши и окружности 10 апр 2007 08:57

I think your are wrong.
Admin's tester for 1103 used integer arithm and absolute
correct now and found your mistake. It means that
your solution gives wrong answers in some situations
and, for example, may lead to crach in technical system.
Therefore we must build right program despite of angry.

Alias (Alexander Prudaev) Re: Problem 1103 "Pensils and Circles" has been rejudged (+) [1] // Задача 1103. Карандаши и окружности 10 апр 2007 10:14

I think administrators are wrong, because this problem has set of interesting solutions,
and complication of a set of tests they reduce this problems to a writing of long real
arithmetics. i think it is not good. to solve this problem you must solve problems of
accuracy of calculations, instead of thinking up algorithm. Besides it is a senseless
step as calculations in any case are inexact

Edited by author 10.04.2007 10:16

Samsonov Alex [USU] Re: Problem 1103 "Pensils and Circles" has been rejudged (+) // Задача 1103. Карандаши и окружности 10 апр 2007 18:11

You are wrong. My solution has a lot of float calculations and still I got AC. The calculations should be just accurate enough and you will have no problem.

[NU GYM] I am get tester... AC!!! // Задача 1103. Карандаши и окружности 3 янв 2006 17:23

Erwin (erwin_hotshot@hotmail.com) if you got wa at #10 in pascal........... [1] // Задача 1103. Карандаши и окружности 4 окт 2004 08:39

Nick Permyakov Has anybody got this problem accepted in C++? [4] // Задача 1103. Карандаши и окружности 28 июн 2005 17:13

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