7621번: Fish Catch

https://www.acmicpc.net/problem/7621

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int MXN = 1e3;
typedef long long ll;
int cx, cy, n, k, idx[MXN], ord[MXN];
ll ax[MXN], ay[MXN], bx[MXN], by[MXN];
double res;
vector<pair<double, pair<int, int> > > v;
pair<double, double> value(ll a, ll b, ll c) {
    if (!a) {
        if (!b) return{ -1,-1 };
        return{ -c*1.0 / b,-1 };
    }
    ll d = b*b - 4 * a*c;
    if (d < 0) return{ -1,-1 };
    return{ (sqrt(d) - b) / a / 2 ,(-sqrt(d) - b) / a / 2 };
}
double rad(int i, double t) {
    return sqrt((ax[i] + bx[i] * t)*(ax[i] + bx[i] * t) + (ay[i] + by[i] * t)*(ay[i] + by[i] * t));
}
int main() {
    scanf("%d%d%d%d", &cx, &cy, &n, &k);
    for (int i = 0; i < n; i++) {
        scanf("%lld%lld%lld%lld", ax + i, ay + i, bx + i, by + i);
        bx[i] -= ax[i];
        by[i] -= ay[i];
        ax[i] -= cx;
        ay[i] -= cy;
        for (int j = 0; j < i; j++) {
            pair<double, double> t = value(bx[i] * bx[i] + by[i] * by[i] - bx[j] * bx[j] - by[j] * by[j],
                2 * (ax[i] * bx[i] + ay[i] * by[i] - ax[j] * bx[j] - ay[j] * by[j]),
                ax[i] * ax[i] + ay[i] * ay[i] - ax[j] * ax[j] - ay[j] * ay[j]);
            if (t.first > 0) v.push_back({ t.first,{ j,i } });
            if (t.second > 0) v.push_back({ t.second,{ j,i } });
        }
        ord[i] = i;
        pair<double, double> t = value(0, bx[i] * bx[i] + by[i] * by[i], ax[i] * bx[i] + ay[i] * by[i]);
        if (t.first > 0) v.push_back({ t.first,{ i,i } });
    }
    sort(ord, ord + n, [](int u, int v) {return rad(u, 0) < rad(v, 0) || rad(u, 0) == rad(v, 0) && rad(u, 1e-9)<rad(v, 1e-9); });
    sort(v.begin(), v.end());
    res = rad(ord[k - 1], 0);
    for (int i = 0; i < n; i++) idx[ord[i]] = i;
    for (auto it : v) {
        swap(ord[idx[it.second.first]], ord[idx[it.second.second]]);
        swap(idx[it.second.first], idx[it.second.second]);
        res = min(res, rad(ord[k - 1], it.first));
    }
    printf("%lf", res);
    return 0;
}