bzoj5099:[POI2018]Pionek(极角排序+two pointers)

Author Avatar
Sakits 5月 31, 2018

题解

  当作存一下极角排序的板子,第一次学…
  极角排序按stl的atan2atan2函数从小到大排序。atan2(y,x)atan2(y,x)即为向量(x,y)(x,y)xx轴正半轴的夹角,对于y<0y<0的向量,定义夹角为负数,故atan2atan2函数值域为[ππ][-\pi \sim \pi]
  此题需要枚举答案向量的方向,那么对这个方向有贡献的向量就是那些在答案向量正方向的向量。
  枚举答案的向量可以倍增后用two pointers,即枚举每个向量作为左端点或者两个向量中间的空隙作为左端点。

代码

#include<iostream> 
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath> 
#include<algorithm>
#define ll long long 
using namespace std;
const int maxn=500010, inf=1e9;
const double eps=1e-7, pi=acos(-1);
struct poi{ll x, y; double a;}q[maxn], sum[maxn];
int n;
ll ans;

template<typename T>
inline void read(T &k)
{
	int f=1; k=0; char c=getchar();
	while(c<'0' || c>'9') c=='-'&&(f=-1), c=getchar();
	while(c<='9' && c>='0') k=k*10+c-'0', c=getchar();
	k*=f;
}

inline ll sqr(ll x){return 1ll*x*x;}

bool operator < (poi a, poi b){return a.a+eps<b.a;} 

inline void getans(int i, int j)
{ans=max(ans, sqr(sum[j-1].x-sum[i-1].x)+sqr(sum[j-1].y-sum[i-1].y));}

int main()
{
	read(n);
	for(int i=1;i<=n;i++) 
	read(q[i].x), read(q[i].y), q[i].a=atan2(q[i].y, q[i].x);
	sort(q+1, q+n+1);
	for(int i=1;i<n;i++) q[i+n]=q[i], q[i+n].a+=2*pi;
	for(int i=1;i<2*n;i++) 
	sum[i].x=sum[i-1].x+q[i].x, sum[i].y=sum[i-1].y+q[i].y;
	for(int i=1, j=1;i<=n;i++)
	{
		while(j-i<n && q[j].a-eps<q[i].a+pi) j++, getans(i, j);
		if(i!=j) getans(i+1, j);
	}
	printf("%lld\n", ans);
}