题解 | 三角谜题

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int N = 1e6 + 10;

map<int, int> f;

void solve() {
    cout << fixed << setprecision(8);
    f.clear();
    int n; cin >> n;
    for (int i = 1; i <= n; i ++ ) {
        int x, y;
        cin >> x >> y;
        f[x] += y;
    }
    vector<int> v1;
    double ans = -1;
    bool flag = false;
    for (auto kv : f) {
        if (kv.second >= 2) {
            v1.push_back(kv.first);
        }
    }
    if (v1.empty()) {
        cout << -1 << endl;
        return ;
    }
    for (auto kv : f) {
        int k = kv.first;
        int v = kv.second;
        int j = v1.size() - 1;
        while (j >= 0 && v1[j] == k && f[v1[j]] == 2) j --;
        if (j < 0) continue;
        int len = v1[j];
        if (len + len <= k) continue;
        double s = (double)k * 0.5 * sqrt(1ll * len * len - 1ll * k * k * 0.25);
        flag = true;
        ans = max(ans, s);
    }
    if (flag) cout << ans << endl;
    else cout << -1 << endl;
}

int main() {
	int T = 1;
    cin >> T;
    while (T -- )
        solve();
	return 0;
}