Submission #2640365

---

Source Code Expand

#include<iostream>
#include<vector>
#include<algorithm>
#include <stdlib.h>

using namespace std;

int count_inversions(int n, vector<pair<double, int > > p) {

    int res = 0;
    vector<int> s(n+1, 0);
    for(int k=0; k < n; k++) {
        int c = 0;
        int u = p[k].second;
        while(u > 0) {
            c += s[u];
            u -= u & (-u);
        }
        u = p[k].second;
        while(u <= n) {
            s[u]++;
            u += u & (-u);
        }
        res += k - c;
    }

    return res;
}

double find_median(int n, vector<int> a, vector<int> b, vector<int> c) {
    int m = n * (n - 1) / 2, target_inversions;

    if (m % 2 == 1)
        target_inversions = (m - 1) / 2;
    else
        target_inversions = m / 2 - 1;

    vector<pair<double, int> > slope(n);
    for(int i=0; i < n; i++) {
        slope[i] = {-a[i] * 1.0 / b[i], i};
    }
    sort(slope.begin(), slope.end());

    vector<pair<double, int> > p(n);

    double inf = 1e9;
    double sa = -inf, sb = inf, s;
    int n_steps = 300;

    for(int step=0; step < n_steps; step++) {
        s = (sa+sb) / 2;
        for(int i=0; i < n; i++) {
            int j = slope[i].second;
            p[i] = {(-a[j] * s + c[j]) / b[j], i + 1};
        }
        sort(p.rbegin(), p.rend());

        int c = count_inversions(n, p);

        if (c > target_inversions) {
            sb = s;
        }
        else {
            sa = s;
        }
    }
    return sa;
}

double find_median_exhaustive(int n, vector<int> a, vector<int> b, vector<int> c) {
    int m = n * (n - 1) / 2, p;

    if (m % 2 == 1)
        p = (m - 1) / 2;
    else
        p = m / 2 - 1;
    vector<double> t(m);

    int k=0;
    for(int i=0; i<n; i++) {
        for(int j=i+1; j<n; j++) {
            double d, dx, dy;
            d  = a[i] * b[j] - a[j] * b[i];
            dx = c[i] * b[j] - c[j] * b[i];
            dy = a[i] * c[j] - a[j] * c[i];
            t[k] = dx / d;

            // cout << "\t" << k << "\t" << t[k] << endl;

            k += 1;

        }
    }

    // for(int k=0; k<m; k++) {
    //     cout << "\t" << k << "\t" << t[k] << endl;
    // }
    // cout << endl;

    sort(t.begin(), t.end());
    return t[p];
}



int solve() {
    int n;
    cin >> n;
    vector<int> a(n), b(n), c(n);
    for(int i=0; i<n; i++)
        cin >> a[i] >> b[i] >> c[i];

    double x, y;
    x = find_median_exhaustive(n, a, b, c);

    y = find_median(n, b, a, c);
    // y = find_median_exhaustive(n, b, a, c);

    cout.precision(12);
    cout << x << " " << y << endl;
    return 0;
}

int check() {

    srand (1);

    int n_steps = 10;
    for(int step = 0; step < n_steps ; step ++) {

        int n = 10000;
        int n_max = 100000 ;
        vector<int> a(n), b(n), c(n);
        for(int i=0; i<n; i++) a[i] = rand() % (2 * n_max) - n_max;
        for(int i=0; i<n; i++) b[i] = rand() % (2 * n_max) - n_max;
        for(int i=0; i<n; i++) c[i] = rand() % (2 * n_max) - n_max;
        double x = find_median(n, a, b, c);
        double y = find_median(n, a, b, c);
        cout << x << " " << y << " " << x - y << endl;
    }
}

int main() {
    solve();
    // check();
}

Submission Info

Judge Result