算法
(几何、贪心) $O(N^2\log N)$
本题其实就是枚举通过选择两点来创建的 $O(N^2)$ 条线段
如果问题是“找一个梯形”,那么我们可以按斜率对线段进行分类;而这里问的是找等腰梯形,所以我们还得要求两线段的中垂线也要相同
我们可以先预处理出斜率相同的线段和中垂线相同的线段
然后贪心的在里面找权重最大的两条线段
注意:需要特判两线段是否重合
C++ 代码
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::gcd;
using std::max;
using std::map;
using std::vector;
using ll = long long;
using P = std::pair<int, int>;
int main() {
int n;
cin >> n;
vector<int> x(n), y(n), c(n);
rep(i, n) cin >> x[i] >> y[i] >> c[i];
map<P, vector<P>> mp;
rep(i, n)rep(j, i) {
int dx = x[i] - x[j], dy = y[i] - y[j];
if (dx == 0) {
dy = 1;
} else {
if (dx < 0) {
dx = -dx;
dy = -dy;
}
int g = gcd(dx, abs(dy));
dx /= g;
dy /= g;
}
mp[P(dx, dy)].emplace_back(i, j);
}
ll ans = -1;
for (auto [a, ps] : mp) {
map<ll, vector<P>> mp2;
for (auto [i, j] : ps) {
ll mx = x[i] + x[j], my = y[i] + y[j];
mp2[mx * a.first + my * a.second].emplace_back(i, j);
}
for (auto [_, ps2] : mp2) {
map<P, int> mp3;
for (auto [i, j] : ps2) {
int mx = x[i] + x[j], my = y[i] + y[j];
mp3[P(mx, my)] = max(mp3[P(mx, my)], c[i] + c[j]);
}
if (mp3.size() < 2) continue;
vector<int> cs;
for (auto [_, nc] : mp3) cs.push_back(nc);
sort(cs.rbegin(), cs.rend());
ans = max(ans, (ll)cs[0] + cs[1]);
}
}
cout << ans << '\n';
return 0;
}