题目链接 Summer Earnings
类似MST_Kruskal的做法，连边后sort。
然后对于每条边，依次处理下来，当发现存在三角形时即停止。（具体细节见代码）
答案即为发现三角形时当前所在边长度的一半。
#include <bits/stdc++.h> using namespace std; struct node{ int x, y, z; friend bool operator < (const node &a, const node &b){ return a.z > b.z; } } p[4600010]; int a[3010], b[3010]; int n, cnt = 0; bitset <3010> c[3010], tmp; int main(){ scanf("%d", &n); for (int i = 1; i <= n; ++i) scanf("%d%d", a + i, b + i); for (int i = 1; i <= n - 1; ++i) for (int j = i + 1; j <= n; ++j) p[++cnt].x = i, p[cnt].y = j, p[cnt].z = (a[i] - a[j]) * (a[i] - a[j]) + (b[i] - b[j]) * (b[i] - b[j]); sort(p + 1, p + cnt + 1); for (int i = 1; i <= cnt; ++i){ int x = p[i].x, y = p[i].y; tmp = c[x] & c[y]; if (tmp.any()) return 0 * printf("%.10f\n", sqrt(1.00 * p[i].z) / 2); c[x].set(y), c[y].set(x); } return 0; }
转载于:https://www.cnblogs.com/cxhscst2/p/6720301.html
相关资源：各显卡算力对照表！