P2900 0pts 代码

#include <algorithm>
#include <deque>
#include <iostream>
#include <vector>

typedef long long LL;
std::deque<LL> Deque, Deque2;
double X[100005], Y[100005], Num[100005];
struct TypeLand {
	LL Length, Width;
} Land[100005];
std::vector<TypeLand> LandVec;

bool CompareFunction(TypeLand A, TypeLand B) {
	if (A.Width != B.Width) return A.Width > B.Width;
	return A.Length > B.Length;
}

double Calc(LL A, LL B) {
	return (Y[A - 1] - Y[B - 1]) / (X[B] - X[A]);
}

LL N;

int main() {
	std::cin >> N;
	for (int i = 1; i <= N; i++) {
		std::cin >> Land[i].Length >> Land[i].Width;
	}
	std::sort(Land + 1, Land + N + 1, CompareFunction);
	LandVec.push_back({0, 0});
	for (int i = 1; i <= N; i++) {
		if (Land[LandVec.size() - 1].Length < Land[i].Length) LandVec.push_back(Land[i]);
	}
	for (int i = 1; i <= LandVec.size() - 1; i++) X[i] = double(Land[i].Width);
	for (int i = 1; i <= LandVec.size() - 1; i++) {
		while (Deque.size() >= 2 && double(Deque2[Deque2.size() - 2]) >= Calc(Deque.back(), i)) {
			Deque.pop_back();
			Deque2.pop_back();
		}
		if (Deque.empty()) {
			Deque2.push_back(LL(Calc(0, i)));
		} else {
			Deque2.push_back(LL(Calc(Deque.back(), i)));
		}
		Deque.push_back(i);
		while (!Deque.empty() && Deque2.front() <= LandVec[i].Length) {
			Deque.pop_front();
			Deque2.pop_front();
		}
		if (!Deque.empty()) {
			Y[i] = double(X[Deque.front()]) * double(LandVec[i].Length) + Y[Deque.front() - 1];
		}
	}
	std::cout << Y[LandVec.size() - 1] << '\n';
	return 0;
}
``