Submission #2640116

---

Source Code Expand

#include<iostream>
#include<vector>
#include<algorithm>
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;

    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;
            k += 1;
        }
    }
    sort(t.begin(), t.end());
    return t[p];
}



int main() {
    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(n, a, b, c);
    y = find_median(n, b, a, c);

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

Submission Info

Judge Result