526互联

AtCoder Beginner Contest 220 G Isosceles Trapezium

发布时间 2023-06-15 21:52:53作者: zltzlt

洛谷传送门

AtCoder 传送门

简单题。

首先肯定是要枚举梯形其中一条底边的两个端点的。那么另一条底边除了斜率与这条边相等，两个端点的距离要分别与这条底边两个端点的距离相等。

发现这个十分不好做，考虑一个梯形是等腰梯形的一个充要条件。不难想到，连接两底中点，这条线段垂直于两条底边。于是除了要满足斜率相等外，还要满足两个点的中点连线的斜率为底边斜率的负倒数。要限定 \(\frac{y_1 - y_2}{x_1 - x_2} = k\)，移项得到 \(y_1 - k x_1 = y_2 - k x_2\)。于是只需限定这一项相等即可。实现时可以用 map。

注意一些细节，为了避免精度问题可以自己手写分数类，而且要特殊处理底边为水平线或竖直线的情况，两底还不能共线（可以把重合的直线放一起处理）。

时间复杂度 \(O(n^2 \log n)\)，常数有点大。

code 
// Problem: G - Isosceles Trapezium
// Contest: AtCoder - AtCoder Beginner Contest 220
// URL: https://atcoder.jp/contests/abc220/tasks/abc220_g
// Memory Limit: 1024 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<ll, ll> pii;

const int maxn = 1010;

struct frac {
	ll x, y;
	frac(ll a = 0, ll b = 1) {
		if (b < 0) {
			a = -a;
			b = -b;
		}
		x = a;
		y = b;
	}
};

inline bool operator < (const frac &a, const frac &b) {
	return a.x * b.y < a.y * b.x;
}

inline bool operator == (const frac &a, const frac &b) {
	return a.x * b.y == a.y * b.x;
}

inline frac operator + (const frac &a, const frac &b) {
	return frac(a.x * b.y + a.y * b.x, a.y * b.y);
}

inline frac operator - (const frac &a, const frac &b) {
	return frac(a.x * b.y - a.y * b.x, a.y * b.y);
}

inline frac operator * (const frac &a, const frac &b) {
	return frac(a.x * b.x, a.y * b.y);
}

ll n;
struct node {
	ll x, y, z;
} a[maxn];

inline frac getb(int i, int j) {
	frac k(a[i].y - a[j].y, a[i].x - a[j].x);
	return frac(a[i].y) - k * frac(a[i].x);
}

void solve() {
	scanf("%lld", &n);
	for (int i = 1; i <= n; ++i) {
		scanf("%lld%lld%lld", &a[i].x, &a[i].y, &a[i].z);
	}
	ll ans = -1;
	sort(a + 1, a + n + 1, [&](node a, node b) {
		return a.x < b.x;
	});
	map<frac, ll> M;
	for (int i = 1, j = 1; i <= n; i = (++j)) {
		while (j < n && a[j + 1].x == a[i].x) {
			++j;
		}
		for (int k = i; k <= j; ++k) {
			for (int l = k + 1; l <= j; ++l) {
				frac mid(a[k].y + a[l].y, 2);
				if (M.find(mid) != M.end()) {
					ans = max(ans, M[mid] + a[k].z + a[l].z);
				}
			}
		}
		for (int k = i; k <= j; ++k) {
			for (int l = k + 1; l <= j; ++l) {
				frac mid(a[k].y + a[l].y, 2);
				M[mid] = max(M[mid], a[k].z + a[l].z);
			}
		}
	}
	M.clear();
	sort(a + 1, a + n + 1, [&](node a, node b) {
		return a.y < b.y;
	});
	for (int i = 1, j = 1; i <= n; i = (++j)) {
		while (j < n && a[j + 1].y == a[i].y) {
			++j;
		}
		for (int k = i; k <= j; ++k) {
			for (int l = k + 1; l <= j; ++l) {
				frac mid(a[k].x + a[l].x, 2);
				if (M.find(mid) != M.end()) {
					ans = max(ans, M[mid] + a[k].z + a[l].z);
				}
			}
		}
		for (int k = i; k <= j; ++k) {
			for (int l = k + 1; l <= j; ++l) {
				frac mid(a[k].x + a[l].x, 2);
				M[mid] = max(M[mid], a[k].z + a[l].z);
			}
		}
	}
	map< frac, vector<pii> > mp;
	for (int i = 1; i <= n; ++i) {
		for (int j = i + 1; j <= n; ++j) {
			if (a[i].x == a[j].x || a[i].y == a[j].y) {
				continue;
			}
			frac k1(a[j].y - a[i].y, a[j].x - a[i].x);
			mp[k1].pb(i, j);
		}
	}
	for (auto pp : mp) {
		frac k1 = pp.fst;
		map<frac, ll> M;
		vector<pii> vc = pp.scd;
		sort(vc.begin(), vc.end(), [&](pii a, pii b) {
			return getb(a.fst, a.scd) < getb(b.fst, b.scd);
		});
		int len = (int)vc.size();
		for (int i = 0, j = 0; i < len; i = (++j)) {
			while (j + 1 < len && getb(vc[j + 1].fst, vc[j + 1].scd) == getb(vc[i].fst, vc[i].scd)) {
				++j;
			}
			for (int k = i; k <= j; ++k) {
				frac mx(a[vc[k].fst].x + a[vc[k].scd].x, 2), my(a[vc[k].fst].y + a[vc[k].scd].y, 2);
				frac k2(-k1.y, k1.x);
				frac fr = my - mx * k2;
				if (M.find(fr) != M.end()) {
					ans = max(ans, M[fr] + a[vc[k].fst].z + a[vc[k].scd].z);
				}
			}
			for (int k = i; k <= j; ++k) {
				frac mx(a[vc[k].fst].x + a[vc[k].scd].x, 2), my(a[vc[k].fst].y + a[vc[k].scd].y, 2);
				frac k2(-k1.y, k1.x);
				frac fr = my - mx * k2;
				M[fr] = max(M[fr], a[vc[k].fst].z + a[vc[k].scd].z);
			}
		}
	}
	printf("%lld\n", ans);
}

int main() {
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}