cs204/postmid1.cpp at master · vikyath664/cs204 · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include<iostream>
#include<algorithm>
#include<climits>
#include<cmath>

using namespace std;

long long int partition(double arr[], long long int l, long long int r, double k);

double findMedian(double arr[], long long int n)
{
    sort(arr, arr+n);
    return arr[n/2];
}

double kthSmallest(double arr[], long long int l, long long int r, long long int k)
{
    if (k > 0 && k <= r - l + 1)
    {
        long long int n = r-l+1;
        long long int i; double median[(n+4)/5];
        for (i=0; i<n/5; i++)
            median[i] = findMedian(arr+l+i*5, 5);
        if (i*5 < n)
        {
            median[i] = findMedian(arr+l+i*5, n%5);
            i++;
        }

        double medOfMed = (i == 1)? median[i-1]:
                                 kthSmallest(median, 0, i-1, i/2);

        int pos = partition(arr, l, r, medOfMed);


        if (pos-l == k-1)
            return arr[pos];
        if (pos-l > k-1)
            return kthSmallest(arr, l, pos-1, k);


        return kthSmallest(arr, pos+1, r, k-pos+l-1);
    }

}

void swap(double *a, double *b)
{
    double temp = *a;
    *a = *b;
    *b = temp;
}


long long int partition(double arr[], long long int l, long long int r, double x)
{

    long long int i;
    for (i=l; i<r; i++)
        if (arr[i] == x)
           break;
    swap(&arr[i], &arr[r]);


    i = l;
    for (long long int j = l; j <= r - 1; j++)
    {
        if (arr[j] <= x)
        {
            swap(&arr[i], &arr[j]);
            i++;
        }
    }
    swap(&arr[i], &arr[r]);
    return i;
}

int main()
{
    long long int n;
    cin>>n;
    while(n--)
    {
        long long int k;
        cin>>k;
        double arr[k];
        for(long long int i=0;i<k;i++)
        {
            long long int x,y;
            cin>>x>>y;
            double d = sqrt(x*x+y*y);
            arr[i] = d;
        }
        cout<<kthSmallest(arr,0,k-1,(k+1)/2)<<'\n';
    }
    return 0;
}