Submission #3015209

---

Source Code Expand

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

struct BIT {
    long long n;
    vector<long long> dat;

    void initialize(long long n_input){
        n = n_input + 1;
        dat.resize(n+1);
        for(int i = 0; i<=n; i++) dat[i] = 0;
    }

    long long sum(long long i){
        long long s = 0;
        while(i >= 0){
            s += dat[i];
            i = (i & (i+1)) - 1;
        }
        return s;
    }

    void add(long long i, long long x){
        while(i <= n){
            dat[i] += x;
            i |= i+1;
        }
    }
};

int inversion(const vector<int> arr){
    BIT bit;
    bit.initialize(arr.size());
    int ret = 0;
    for(int i=0; i<arr.size(); i++){
        ret += i - bit.sum(arr[i]);
        bit.add(arr[i], 1);
    }
    return ret;
}

vector<vector<int>> abc;
double mid;

bool cmpx(int a, int b){
    double aa = (double)(-abc[a][0]*mid+abc[a][2]) / abc[a][1];
    double bb = (double)(-abc[b][0]*mid+abc[b][2]) / abc[b][1];
    return aa < bb;
}

bool cmpy(int a, int b){
    double aa = (double)(-abc[a][1]*mid+abc[a][2]) / abc[a][0];
    double bb = (double)(-abc[b][1]*mid+abc[b][2]) / abc[b][0];
    return aa < bb;
}

bool cmpdx(vector<int> a, vector<int> b){
    double aa = (double)a[0] / a[1];
    double bb = (double)b[0] / b[1];
    return aa < bb;
}

bool cmpdy(vector<int> a, vector<int> b){
    double aa = (double)a[1] / a[0];
    double bb = (double)b[1] / b[0];
    return aa < bb;
}

int main(){
    long long i, j, k;
    int N;
    cin >> N;
    abc.resize(N);
    for(i=0; i<N; i++){
        int a, b, c;
        cin >> a >> b >> c;
        abc[i] = {a, b, c};
    }
    int half = (N*(N-1)/2+1)/2;

    vector<int> order(N);
    for(i=0; i<N; i++) order[i] = i;

    sort(abc.begin(), abc.end(), cmpdx);
    double ub = 1e9, lb = -1e9;
    for(i=0; i<70; i++){
        mid = (ub+lb)/2;
        sort(order.begin(), order.end(),cmpx);
        int inv = inversion(order);
        if(inv<half){
            lb = mid;
        }else{
            ub = mid;
        }
    }
    double x = ub;

    sort(abc.begin(), abc.end(), cmpdy);
    ub = 1e9, lb = -1e9;
    for(i=0; i<70; i++){
        mid = (ub+lb)/2;
        sort(order.begin(), order.end(),cmpy);
        int inv = inversion(order);
        if(inv<half){
            lb = mid;
        }else{
            ub = mid;
        }
    }
    double y = ub;

    cout << fixed << setprecision(10);
    cout << x << " " << y << endl;
    return 0;
}

Submission Info

Judge Result