[BZOJ5099]Pionek

Description

给 \(n\) (\(n\le 2\times 10 ^5\)) 个向量，现在你在 \((0,0)\) ，选择一些向量使你走的最远。

Solution

自己的想法：按极角排序后双指针 \(l, r\) 扫，若选择 \(r + 1\) 向量走的更远就 r++ ，否则 l++ ，用 \([l,r]\) 的向量和与答案 \(chkmax\)。

这样是错的，虽然答案最后一定是一段连续的区间，但这个并不满足局部最优，所以可能 \(r\) 指针需要舍弃一些不优的右移而到一个更好的位置。

题解首先按极角排序，然后答案一定是某一个半平面，即选一根过原点的x轴，x正半轴的向量都选，也是双指针扫一遍即可。

code

#include <iostream>

#include <cstdio>

#include <cmath>

#include <cstring>

#include <algorithm>

#include <fstream>

typedef long long LL;

typedef unsigned long long uLL;

#define SZ(x) ((int)x.size())

#define ALL(x) (x).begin(), (x).end()

#define MP(x, y) std::make_pair(x, y)

#define DEBUG(...) fprintf(stderr, __VA_ARGS__)

#define GO cerr << "GO" << endl;

using namespace std;

inline void proc_status()

{

	ifstream t("/proc/self/status");

	cerr << string(istreambuf_iterator<char>(t), istreambuf_iterator<char>()) << endl;

}

template<class T> inline T read()

{

	register T x = 0; register int f = 1; register char c;

	while (!isdigit(c = getchar())) if (c == '-') f = -1;

	while (x = (x << 1) + (x << 3) + (c xor 48), isdigit(c = getchar()));

	return x * f;

}

template<typename T> inline bool chkmin(T &a, T b) { return a > b ? a = b, 1 : 0; }

template<typename T> inline bool chkmax(T &a, T b) { return a < b ? a = b, 1 : 0; }

const int maxN = (int) 2e5;

const double PI = acos(-1);

struct Vector

{

	int x, y;

	double angle;

	Vector(int x = 0, int y = 0) : x(x), y(y) { angle = atan2(y, x); }

	bool operator < (const Vector& B) const { return angle < B.angle; }

	Vector operator + (const Vector& B) const { return Vector(x + B.x, y + B.y); }

	Vector operator - (const Vector& B) const { return Vector(x - B.x, y - B.y); }

} ;

int n;

Vector vec[maxN * 2 + 2];

void Input()

{

	n = read<int>();

	for (int i = 1; i <= n; ++i)

	{

		int x = read<int>(), y = read<int>();

		vec[i] = Vector(x, y);

	}

}

void Init()

{

	sort(vec + 1, vec + 1 + n);

	for (int i = 1; i <= n; ++i) vec[i + n] = vec[i], vec[i + n].angle += 2 * PI;

	n <<= 1;

}

LL dis(Vector cur) { return (LL)cur.x * cur.x + (LL)cur.y * cur.y; }

void Solve()

{

	LL ans(0);

	Vector cur(0, 0);

	for (int i = 1, j = 1; j <= n / 2; ++j)

	{

		while (i < n + j and vec[i].angle - vec[j].angle < PI)

			cur = cur + vec[i++], chkmax(ans, dis(cur));

		cur = cur - vec[j];

		chkmax(ans, dis(cur));

	}

	printf("%lld\n", ans);

}

int main()

{

#ifndef ONLINE_JUDGE

	freopen("BZOJ5099.in", "r", stdin);

	freopen("BZOJ5099.out", "w", stdout);

#endif

	Input();

	Init();

	Solve();

	return 0;

}

巴特西

[BZOJ5099]Pionek

Description

Solution

code

最新文章

热门文章