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

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

Why do they want me to do?
How to understand "equal-sized parts"?

//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...

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

3
0 0
0 1
1 0
?

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

Edited by author 28.05.2012 21:59

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

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.

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 /*  */

It's 1-st point and two others.

What is in test 9?

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