I made all my coordinate variables double, so I had a bug when I printed it out :(
cout << (int)x << ' ' << int(y) << '\n'; -> fixed my bug

5
0 -100000000
1 -100000000
1 -99999999
-1 100000000
0 100000000
I think, this answer is wrong:
0 -100000000
1 -100000000
-1 100000000
But my AC program doesn't think so.

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

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

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

my program with
while(n < 3)
 printf("there are some stupid tests!\n");
gets Output limit exceeded 3.
Please, check your tests!

how about the test4???

Edited by author 01.07.2009 09:47

Could you help me?! :/

Can anyone tell me what the test #2 include? Please send to my email vietlong2110@gmail.com

My solution resulted in Crash {FLT_INVALID_OPERATION} several times, before I understood, that the square of an integer number can be negative!

Oh! What a stupid mistake!-)

The crash mentioned above was caused by the following function in my source code:

function Dist( const p1, p2: Point ): extended;
begin
    Result := sqrt( sqr(p2.x-p1.x) + sqr(p2.y-p1.y) );
end;

I couldn't even imagine, that sqr() function can produce negative results!

So, If you get Crash on test #6, just use extended (^:

1. there are always solutions.
2. convex polygon. but don't need to find.

Edited by author 10.12.2005 05:18

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

I have two solutions.
The first easily gets AC, and the second passes stress test with the first but fails on the 12-th test.

If you know the 12-th test or some special cases for this problem, my email is sk1@hotbox.ru.

------------------
Sergey Kopeliovich

Give me some critical I/O please.
I use long arithmetic, so there is no presicion error.

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

Edited by author 24.10.2006 10:47

AC!!!
time 0.4

It is very beautiful problem.
I am happy, that I spent 1 hour for it.

use extended

It may be impossible to solve this problem in C++ using floating-point math because long double is double in this brain-damaged compiler.