Help please!! What is test 6????

import math
import operator

n = int(input())

s = input()
l1 = s.split(" ")
x = int(l1[0])
y = int(l1[1])

sp = {}


for i in range(n-1):
    s = input().split(" ")
    x1 = int(s[0])
    y1 = int(s[1])
    dx = x1-x
    dy = y1-y
    dl = math.sqrt(math.pow(dx,2)+math.pow(dy,2))
    a = math.degrees(math.asin(dy/dl))
    #print(a)
    sp.update({i+2:a})

sorted_tuples = sorted(sp.items(), key=operator.itemgetter(1))
#print(sorted_tuples)
print("1")
print(sorted_tuples[len(sorted_tuples)//2][0])

UPD: i have find mistake

Edited by author 13.08.2020 00:16

#include <bits/stdc++.h>
using namespace std;

int const N = 123456;
#define pi acos(-1.0)
typedef long long ll;

int ar[N],xar[N],uses[N];

struct points {
     double x, y;
     int id;
     points() {}
     points(double x, double y) : x(x), y(y) {}
 } ;

double ang(const points &p){
    double res = atan2(p.y, p.x);
    if(res < 0) res += 2.0 * pi;
    return res;
}

struct cmp{
    inline bool operator () (const points &p1, const points &p2){
        double ang1 = ang(p1)*(180/pi), ang2 = ang(p2)*(180/pi);
        if(fabs(ang1 - ang2) < 1e-9){
            ll d1 = (ll)p1.x * (ll)p1.x + (ll)p1.y * (ll)p1.y;
            ll d2 = (ll)p2.x * (ll)p2.x + (ll)p2.y * (ll)p2.y;

            return d1 < d2;
        }
        return ang1 < ang2;
    }
};

points pt[N];

int main() {
    int n;
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> pt[i].x >> pt[i].y;
        pt[i].id = i+1;
    }
    sort(pt, pt+n, cmp());
    cout<<pt[0].id<<" "<<pt[(n/2)].id<<endl;

    return 0;
}

//1152
#include <iostream>
#include <vector>
#include <cmath>


using namespace std;

int main() {
    int n, x0, y0, index0;
    cin >> n;
    if (n == 2){
        cout << 1 + ' ' + 2;
    } else {
        vector<vector<int>> p(n, vector<int>(2)); // [x, y]
        vector<double> k(n);
        for (int i = 0; i < n; i++) {
            cin >> p[i][0] >> p[i][1];
        }

        x0 = y0 = 2147483647;
        for (int i = 0; i < n; i++) {
            if (p[i][0] < x0 ||p[i][0] == x0 && p[i][1] < y0){
                x0 = p[i][0];
                y0 = p[i][1];
                index0 = i;
                }
        }

        for (int i = 0; i < n; i++) { //y = kx + m
            if (i == index0) {
                k[i] = 9223372036854775807;
            } else {
                if (x0 == p[i][0]) {
                    k[i] = 9223372036854775807;
                } else {
                    k[i] = (p[i][1] - y0) / (p[i][0] - x0);
                }
            }
        }


        vector<int> d(n);
        for (int i = 0; i < n; i++) {
            d[i] = i;
        }

        double tempD;
        int tempI;
        for (int i = n - 1; i >= 0; i--) {
            for (int j = 0; j < i; j++) {
                if (k[j + 1] < k[j]) {

                    tempD = k[j + 1];
                    k[j + 1] = k[j];
                    k[j] = tempD;

                    tempI = d[j + 1];
                    d[j + 1] = d[j];
                    d[j] = tempI;

                }
            }
        }
        cout << index0 + 1 << ' ' << d[n / 2  -1] + 1;
    }
return 0;
}

What is test #3?

using System;

class point{
    public int x, y, id;
}

class EntryPoint
{
    static void Main()
    {
        point[] v=new point [10001];
        int n = Convert.ToInt32(Console.ReadLine());
        int min_i=0;
        int min = 20000000;
        for (int i = 0; i < n; i++)
        {
            v[i] = new point();
            string[] str = Console.ReadLine().Split(' ');
            v[i].x = Convert.ToInt32(str[0]);
            v[i].y = Convert.ToInt32(str[1]);
            v[i].id = i+1;
            if (v[i].y < min)
            {
                min = v[i].y;
                min_i = i;
            }
        }
        swap(ref v[0], ref v[min_i]);
        for (int i = 0; i < n; i++)
        {
            v[i].x -= v[i].x;
            v[i].y -= v[i].y;
        }
        fast_sort(v,0,n-1);
        Console.WriteLine(min_i+1+" "+v[n/2+1].id);
    }

    static int fync(point a, point b)
    {
        if ((a.x > 0) && (b.y == 0)) return 1;
        if (a.x * b.y < a.y * b.x) return 1;
        return 0;
    }
    static void swap(ref point a, ref point b)
    {
        point tmp;
        tmp = a;
        a = b;
        b = a;
    }
    static void fast_sort(point[] arr,int low,int high)
    {
        int i,j;
        int x;
        i = low;
        j = high;
        x = arr[(i + j) / 2].y;
        do
        {
            while (arr[i].y < x) ++i;
            while (arr[j].y > x) --j;
            if (i <= j)
            {
                int temp = arr[i].y;
                arr[i].y = arr[j].y;
                arr[j].y = temp;
                i++; j--;
            }
        } while (i <= j);
        if (low < j) fast_sort(arr,
            low, j);
        if (i < high) fast_sort(arr, i, high);
    }
}

My last submission (4829935) got AC, but I think this algo is wrong. For example, for test
8
0 0
3 -2
1 -3
-1 -5
-3 -3
-3 1
-5 6
3 1
it gives 1 5. Actually, I have no idea how it can get AC...

3
0 0
0 1
1 0
?

Oh, sorry, of course not, because n is even.

Edited by author 28.05.2012 21:59

I solved using too mush time
Can anyone explain me how some people did it in 0.031??
Please)

if you have WA 5 try changing all data types to long long(int64)
same i guess goes for other languages
I had int for coordinates and got WA 5 and then just changed it to long long and AC

mycode:
#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;
#define N 10002
struct node
{
    double  x,y;
    int num;
}point[N];
int n;
int cmp(node a,node b)
{
    double pp=atan2(a.y-point[0].y,a.x-point[0].x);
    double qq=atan2(b.y-point[0].y,b.x-point[0].x);
    //double pp=(a.x-point[0].x)*(b.y-point[0].y)-(a.y-point[0].y)*(b.x-point[0].x);
    return pp>qq;
}
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%lf%lf",&point[i].x,&point[i].y);
        point[i].num=i+1;
    }
    int pos=0;
    /*for(int i=1;i<n;i++)
    {
        if(point[i].x<point[pos].x||(point[i].x==point[pos].x)&&point[i].y<point[pos].y)
        pos=i;
    }
    swap(point[0],point[pos]);*/
    sort(point+1,point+n,cmp);
    printf("%d %d\n",point[0].num ,point[n/2].num);
    return 0;
}
what it`s function in /*  */

Just be careful with the angles.

type
    point=record x,y:longint; end;
var
    vert:array[1..10000] of point;
    visited:array[1..10000] of byte;
    min:point;
    n,i,k,imin,minvert:integer;
Procedure Search_Min_Polar_Angle;
var
    i:integer;
    min_angle,angle,tg,a,b:real;
begin
    min_angle:=pi;
    for i:=1 to n do
        if (visited[i]=0) then
            begin
                a:=(vert[i].y-vert[imin].y);
                b:=(vert[i].x-vert[imin].x);
                if (b=0) then angle:=pi/2
                         else
                begin
                    tg:=a/b;
                    angle:=arctan(tg);
                end;
                if (angle<min_angle) then
                    begin min_angle:=angle; minvert:=i; end;
            end;
    visited[minvert]:=1;
end;

Begin
    readln(n);
    for i:=1 to n do visited[i]:=0;

    // naxojdenie samoy nijney levoy to4ki
    min.y:=maxlongint;
    for i:=1 to n do
        begin
            readln(vert[i].x,vert[i].y);
            if (vert[i].y<min.y) then
                begin min:=vert[i]; imin:=i; end
            else
            if (vert[i].y=min.y) and (vert[i].x<min.x) then
                begin min:=vert[i]; imin:=i; end;
        end;
    visited[imin]:=1;
    //-----------------------------------

    for k:=1 to n div 2 do Search_Min_Polar_Angle;
    writeln(imin,' ',minvert);
End.

Edited by author 09.05.2010 19:47

Can it be solved using qsort+n*bs(on x coordinates of points)
greetings

program p1207;
uses math;
type
  realer=record
           rr:real;
           num:longint;
         end;
var
  i,j,k,n,m,x,y,x0,y0:longint;
  r:array[1..10000]of realer;
procedure qs(h,t:longint);
  var
    i,j:longint;
    k:real;
    o:realer;
  begin
    if h>=t
      then exit;
    i:=h;j:=t;k:=r[(i+j)div 2].rr;
    repeat
      while r[i].rr<k do
        inc(i);
      while r[j].rr>k do
        dec(j);
      if i<=j
        then begin
          o:=r[i];
          r[i]:=r[j];
          r[j]:=o;
          inc(i);
          dec(j);
        end;
    until i>j;
    qs(h,j);
    qs(i,t);
  end;
begin
  readln(n);
  readln(x0,y0);
  for i:=2 to n do
    begin
      readln(x,y);
      x:=x-x0;
      y:=y-y0;
      if x=0
        then
          if y>0
            then r[i-1].rr:=0.5*pi
            else r[i-1].rr:=-0.5*pi
        else r[i-1].rr:=arctan(y/x);
      r[i-1].num:=i;
    end;
  qs(1,n-1);
  writeln(1,' ',r[n div 2].num);
end.

#include <iostream>
using namespace std;
#include <math.h>

struct Point
{
    long double x;
    long double y;
};
struct Point2
{
    int number;
    long double angle;
};
void insertSort(Point2 ** a, long size) {
  Point2 * x;
  long i, j;

  for ( i=0; i < size; i++) {  // цикл проходов, i - номер прохода
    x = a[i];

    // поиск места элемента в готовой последовательности
    for ( j=i-1; j>=0 && (a[j]->angle < x->angle); j--)
      a[j+1] = a[j];      // сдвигаем элемент направо, пока не дошли

    // место найдено, вставить элемент
    a[j+1] = x;
  }
}
/*
int compare( const void *arg1, const void *arg2 )
{
   if(((Point2*)arg1)->angle>((Point2*)arg2)->angle)
       return -1;
   else
        return 1;

}*/
int main()
{

    int n;
    cin>>n;
    Point * arr = new Point[n];
    long double min_a=0;
    int min_ai;
    for(int i = 0;i<n;++i)
    {
        cin>>arr[i].x;
        cin>>arr[i].y;
        if((!i)||arr[i].y<min_a)
        {
            min_a = arr[i].y;
            min_ai = i;
        }
    }
    cout<<min_ai+1<<" ";
    Point2 ** arr2 = new Point2*[n-1];
    int j = 0;
    long double xx = arr[min_ai].x;
    long double yy = arr[min_ai].y;
    for(int i = 0;i<n;++i)
    {
        if(i!=min_ai)
        {
            arr2[j] = new Point2;
            arr2[j]->number = i;
            arr2[j]->angle =  (arr[i].x - xx)/sqrt(pow(arr[i].x-xx,2)+pow(arr[i].y-yy,2));
            ++j;

        }
    }
    //qsort(arr2,n-1,4,compare);
    insertSort(arr2,n-1);
    cout<<arr2[(n-1)/2]->number+1<<endl;
    return 0;
}

I don't know why, but qsort sorts them wrongly (I commented part that is qsort and changed it with simple O(n^2) sorting and got AC... But could tell me, what's so wrong with this qsort? I think I could get a better time with it.

Cross plot+Qsort

var i,j,n,b2,n0,mid:integer;
x,y,al:array[1..10000] of real; num:array[1..10000] of integer;

begin
readln(n);
for i:=1 to n do begin
readln(x[i],y[i]);
num[i]:=i;
end;

n0:=1;
for i:=1 to n do begin
if x[i]<x[n0] then n0:=i;
if (x[i]=x[n0]) and (y[i]<y[n0]) then n0:=i;
end;

for i:=1 to n do
if i<>n0 then begin
if x[i]=x[n0] then al[i]:=pi/2
else al[i]:=arctan((y[i]-y[n0])/(x[i]-x[n0]))
end;

for i:=1 to n-1 do         {Sorting by angle}
for j:=i+1 to n do
if (al[j]<al[i]) and (i<>n0) and (j<>n0) then begin
b2:=num[i]; num[i]:=num[j]; num[j]:=b2; end;

for i:=1 to n div 2 do if i<>n0 then inc(mid) else inc(mid,2);
writeln(num[n0],' ',num[mid]);
end.

Edited by author 05.01.2009 13:11

Edited by author 05.01.2009 13:12