自动搬运

查看原文

来自洛谷，原作者为

	Alex_Wei **

搬运于2025-08-24 22:35:59，当前版本为作者最后更新于2022-02-05 09:54:03，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P8101 [USACO22JAN] Multiple Choice Test P

对于没见过套路的新手，是好题；对于见多识广的高手，是套路题。

关键结论：可能成为答案的点一定在凸包上。根据 $x ^ 2$ 的凸性容易证明。接下来就好做了。考虑对每组向量均建出凸包，求出这 $n$ 个凸包的闵可夫斯基和，最后用大凸包上的点更新答案。

大小为 $a$ 和大小为 $b$ 的凸包的闵可夫斯基和需要 $\mathcal{O}(a + b)$ 时间计算，因此考虑启发式合并。视向量总数与 $n$ 同级，时间复杂度为 $\mathcal{O}(n\log n)$。

更为厉害的做法：考虑我们对两个凸包做闵可夫斯基和的过程，就是把所有边拿出来归并排序，再塞回去，这个过程 不改变边本身。因此，我们直接把所有凸包的所有边拿出来，极角排序，再塞回去，就不需要启发式合并的过程了，相当于同时求多个凸包的闵可夫斯基和。时间复杂度也是线性对数，但是比上个做法高妙多了。

代码分别是启发式合并和直接对边排序，后者借鉴了 Benq 在极角排序上的处理。

• upd：对错误代码进行更新，详见 https://www.luogu.com.cn/discuss/417389。

#include <bits/stdc++.h>
using namespace std;

#define ll long long
const int N = 2e5 + 5;

struct Pt {
	int x, y;
	bool operator < (const Pt &rhs) {return x != rhs.x ? x < rhs.x : y < rhs.y;}
	Pt operator + (const Pt &rhs) {return {x + rhs.x, y + rhs.y};}
	Pt operator - (const Pt &rhs) {return {x - rhs.x, y - rhs.y};}
	ll norm() {return 1ll * x * x + 1ll * y * y;}
	ll cross(const Pt &rhs) {return 1ll * x * rhs.y - 1ll * y * rhs.x;}
	void print(string info = "") {cout << info << " " << x << " " << y << endl;}
};

void print(vector <Pt> &v, string info) {
	cout << "print convex hull : " << info << "\n";
	for(auto it : v) cout << it.x << " " << it.y << "\n";
	cout << "finished.\n";
}

ll n, ans;
vector <Pt> c[N]; Pt cen;
set <pair <int, int>> s;
bool cmp(Pt x, Pt y) {
	ll res = (x - cen).cross(y - cen);
	if(res) return res > 0;
	return (x - cen).norm() > (y - cen).norm();
}
void ConvexHull(vector <Pt> &v) {
	static Pt stc[N]; int top = 0;
	for(int i = 1; i < v.size(); i++) if(v[i] < v[0]) swap(v[i], v[0]);
	cen = stc[top = 1] = v[0], sort(v.begin() + 1, v.end(), cmp);
	for(int i = 1; i < v.size(); i++) {
		while(top >= 2 && (stc[top] - stc[top - 1]).cross(v[i] - stc[top]) < 0) top--;
		stc[++top] = v[i];
	} v.clear(), assert(v.size() == 0);
	for(int i = 1; i <= top; i++) v.push_back(stc[i]);
}

vector <Pt> operator + (vector <Pt> &lhs, vector <Pt> &rhs) {
	vector <Pt> ret; ret.push_back(lhs[0] + rhs[0]);
	static Pt sl[N], sr[N]; int pl = 0, pr = 0, L = lhs.size(), R = rhs.size();
	for(int i = 0; i < L; i++) sl[i] = lhs[(i + 1) % L] - lhs[i];
	for(int i = 0; i < R; i++) sr[i] = rhs[(i + 1) % R] - rhs[i];
	while(pl < L && pr < R) ret.push_back(ret.back() + (sl[pl].cross(sr[pr]) > 0 || sl[pl].cross(sr[pr]) == 0 && sl[pl].x > sr[pr].x ? sl[pl++] : sr[pr++]));
	while(pl < L) ret.push_back(ret.back() + sl[pl++]);
	while(pr < R) ret.push_back(ret.back() + sr[pr++]);
	return ret.pop_back(), ret;
}

int main() {
	cin >> n;
	for(int i = 1, k, x, y; i <= n; i++) {
		scanf("%d", &k);
		while(k--) cin >> x >> y, c[i].push_back({x, y});
		ConvexHull(c[i]), s.insert({c[i].size(), i});
	} while(s.size() > 1) {
		int a = s.begin() -> second, b = (++s.begin()) -> second;
		s.erase(s.begin()), s.erase(s.begin());
		c[a] = c[a] + c[b], s.insert({c[a].size(), a});
	} for(auto it : c[s.begin() -> second]) ans = max(ans, it.norm());
	assert(c[s.begin() -> second].size() <= 2e5);
	cout << ans << endl;
	return 0;
}

#include <bits/stdc++.h>
using namespace std;

#define ll long long
const int N = 2e5 + 5;

struct Pt {
	int x, y;
	bool operator < (const Pt &rhs) {return x != rhs.x ? x < rhs.x : y < rhs.y;}
	Pt operator + (const Pt &rhs) {return {x + rhs.x, y + rhs.y};}
	Pt operator - (const Pt &rhs) {return {x - rhs.x, y - rhs.y};}
	ll norm() {return 1ll * x * x + 1ll * y * y;}
	ll cross(const Pt &rhs) {return 1ll * x * rhs.y - 1ll * y * rhs.x;}
	bool dir() {return x > 0 || (x == 0 && y > 0);}
} off[N];

ll n, cnt, ans;
vector <Pt> c; Pt cen, start;
bool cmp(Pt x, Pt y) {
	ll res = (x - cen).cross(y - cen);
	if(res) return res > 0;
	return (x - cen).norm() > (y - cen).norm();
}
void ConvexHull(vector <Pt> &v) {
	static Pt stc[N]; int top = 0;
	for(int i = 1; i < v.size(); i++) if(v[i] < v[0]) swap(v[i], v[0]);
	cen = stc[top = 1] = v[0], sort(v.begin() + 1, v.end(), cmp);
	for(int i = 1; i < v.size(); i++) {
		while(top >= 2 && (stc[top] - stc[top - 1]).cross(v[i] - stc[top]) < 0) top--;
		stc[++top] = v[i];
	} for(int i = (v.clear(), 1); i <= top; i++) v.push_back(stc[i]);
}

int main() {
	cin >> n;
	for(int i = 1, k, x, y; i <= n; i++) {
		scanf("%d", &k), c.clear();
		while(k--) cin >> x >> y, c.push_back({x, y});
		ConvexHull(c), start = start + c[0];
		for(int i = 1; i <= c.size(); i++) off[++cnt] = c[i % c.size()] - c[i - 1];
	}
	sort(off + 1, off + cnt + 1, [&](Pt x, Pt y) {return x.dir() != y.dir() ? x.dir() : x.cross(y) > 0;});
	for(int i = 1; i <= cnt; i++) ans = max(ans, start.norm()), start = start + off[i];
	cout << ans << endl;
	return 0;
}