萌新刚学OI,叉积求极角序97ptsQWQ
查看原帖
萌新刚学OI,叉积求极角序97ptsQWQ
788951
TLE_AK楼主2024/7/15 20:24
#include<bits/stdc++.h>
using namespace std;
#define int long long

namespace acac
{
	const double eps=1e-10;
	int bs(double x)
	{
		return (x<0?-x:x)<=eps?0:(x<0?-1:1);
	}
	struct vector
	{
		int x,y;
		int col,ud;
	}P[400010],ys;
	vector operator+(const vector &A,const vector &B)
	{
		vector C={A.x+B.x,A.y+B.y}; 
		return C;
	}
	vector operator-(const vector &A,const vector &B)
	{
		vector C={A.x-B.x,A.y-B.y}; 
		return C;
	}
	
	double det(vector A,vector B)
	{
		return A.x*B.y-A.y*B.x;
	}
	
	bool cmp(vector a,vector b)
	{
		if(a.ud!=b.ud)return a.ud<b.ud;
		if(!bs(det(a,b)))return a.x<b.x;
		return det(a,b)>0;
	}
	
	int main()
	{
		int n,ans=0,y1=0;
		scanf("%lld",&n);

		for(int i=1;i<=n;i++)
		{
			scanf("%lld%lld",&P[i].x,&P[i].y);
			if(P[i].y<0||(!P[i].y&&P[i].x>0))P[i].ud=1;
			if(!P[i].y&&!P[i].x)P[i].ud=2,y1++;
		}
		
		sort(P+1,P+1+n,cmp);
		n-=y1;
		int l=1,r=1,sx=0,sy=0;
		for(int i=1;i<=n;i++)
		{
			P[i+n]=P[i];
		}
		for(l=1;l<=n;l++)
		{
			while(r<n+l&&det(P[l],P[r])>=0)
			{
				sx+=P[r].x,sy+=P[r].y;
				r++;
				ans=max(ans,sx*sx+sy*sy);
			}
			sx-=P[l].x,sy-=P[l].y;
			ans=max(ans,sx*sx+sy*sy);
		}	
	
		sx-=P[l].x,sy-=P[l].y;
			ans=max(ans,sx*sx+sy*sy);
			cout<<ans;
		return 0;
	}
}
#undef int
int main()
{
	acac::main();
	return 0;
}
2024/7/15 20:24
加载中...