[POI2018]Pionek

题目大意：

在无限大的二维平面的原点放置着一个棋子。你有\(n(n\le2\times10^5)\)条可用的移动指令，每条指令可以用一个二维整数向量表示。请你选取若干条指令，使得经过这些操作后，棋子离原点的距离最大。

思路：

将所有向量极角排序，然后你选取的向量一定是里面连续的一段，由于所有向量排成一个环，所以要复制一遍接在后面，最后用尺取法枚举左右端点即可。

时间复杂度\(\mathcal O(n\log n)\)。

源代码：

#include<cmath>

#include<cstdio>

#include<cctype>

#include<algorithm>

inline int getint() {

	register char ch;

	register bool neg=false;

	while(!isdigit(ch=getchar())) neg|=ch=='-';

	register int x=ch^'0';

	while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');

	return neg?-x:x;

}

typedef long long int64;

const int N=4e5+2;

struct Point {

	int64 x,y;

	double a;

	bool operator < (const Point &rhs) const {

		return a<rhs.a;

	}

	Point operator + (const Point &rhs) const {

		return (Point){x+rhs.x,y+rhs.y,a+rhs.a};

	}

};

Point p[N],sum[N];

inline int64 sqr(const int64 &x) {

	return x*x;

}

int main() {

	const int n=getint();

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

		p[i].x=getint();

		p[i].y=getint();

		p[i].a=atan2(p[i].x,p[i].y);

	}

	std::sort(&p[1],&p[n]+1);

	std::copy(&p[1],&p[n]+1,&p[n+1]);

	for(register int i=n+1;i<=n*2;i++) {

		p[i].a+=M_PI*2;

	}

	int64 ans=0;

	sum[n*2].a=1e8;

	for(register int i=1,j=1;j<=n*2;j++) {

		sum[j]=sum[j-1]+p[j];

		for(;i<=j&&p[j+1].a-p[i].a>=M_PI;i++) {

			ans=std::max(ans,sqr(sum[j].x-sum[i-1].x)+sqr(sum[j].y-sum[i-1].y));

		}

		if(i<=j) ans=std::max(ans,sqr(sum[j].x-sum[i-1].x)+sqr(sum[j].y-sum[i-1].y));

	}

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

	return 0;

}