Submission #1689914

---

Source Code Expand

#include "bits/stdc++.h"
using namespace std;
#define FOR(i,j,k) for(int (i)=(j);(i)<(int)(k);++(i))
#define rep(i,j) FOR(i,0,j)
#define each(x,y) for(auto &(x):(y))
#define mp make_pair
#define mt make_tuple
#define all(x) (x).begin(),(x).end()
#define debug(x) cout<<#x<<": "<<(x)<<endl
#define smax(x,y) (x)=max((x),(y))
#define smin(x,y) (x)=min((x),(y))
#define MEM(x,y) memset((x),(y),sizeof (x))
#define sz(x) (int)(x).size()
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;

template<class Val>
struct BinaryIndexedTree {
    int n;
    vector<Val> t;
    BinaryIndexedTree() {}
    BinaryIndexedTree(int _n) :n(_n + 1), t(_n + 1) {}
    void add(int k, Val val) {
        k++;
        while (k < n) {
            t[k] += val;
            k += (k&-k);
        }
    }
    void set(int k, Val val) {
        add(k, -sum(k, k + 1));
        add(k, val);
    }
    Val sum(int k) {
        Val r = 0;
        while (k > 0) {
            r += t[k];
            k -= (k&-k);
        }
        return r;
    }
    Val sum(int l, int r) {
        return sum(r) - sum(l);
    }
};
typedef BinaryIndexedTree<int> BIT;

bool cmp(pair<int, int> a, pair<int, int> b) {
    return 1ll*a.first*b.second<1ll*b.first*a.second;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    int N;
    cin >> N;

    vi A(N), B(N), C(N);
    rep(i, N)cin >> A[i] >> B[i] >> C[i];

    const int need = (N*(N - 1) / 2 + 1) / 2;
    auto f = [&](vi a, vi b, vi c) {
        vector<pii> di(N);
        rep(i, N) {
            if (b[i] < 0)a[i] *= -1, b[i] *= -1, c[i] *= -1;
            di[i] = mp(-a[i], b[i]);
        }
        sort(all(di));
        di.erase(unique(all(di)), di.end());
        sort(all(di), cmp);

        double lb = -1e16, ub = 1e16, x;
        rep(ITER, 100) {
            x = (lb + ub)*0.5;
            BIT bit(N);
            vector<pair<double, int> > ry(N);
            rep(i, N) {
                ry[i] = mp((-a[i]*x+c[i])/b[i], i);
            }
            sort(all(ry));
            int cnt = 0;
            rep(k, N) {
                int ly, i;
                i = ry[k].second;
                ly = lower_bound(all(di), mp(-a[i], b[i]), cmp) - di.begin();
                cnt += bit.sum(0, ly);
                bit.add(ly, 1);
            }
            (cnt >= need ? ub : lb) = x;
        }
        return ub;
    };

    double x = f(A, B, C), y = f(B, A, C);

    cout << fixed << setprecision(20) << x << ' ' << y << endl;
}

Submission Info

Judge Result