社区讨论

WA+TLE 60pts 求助

P3217[HNOI2011] 数矩形参与者 7已保存回复 6

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
6 条
当前快照
1 份
快照标识符
@mjfqt93w
此快照首次捕获于
2025/12/21 21:08
2 个月前
此快照最后确认于
2025/12/24 18:45
2 个月前
查看原帖
RT,code:
CPP
#include<unordered_map>
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
struct point
{
	int x,y;
	point(){}
	point(int x,int y):x(x),y(y){}
	long long dis() const {return x*1ll*x+y*1ll*y;}
	bool dir() const {return (x>0) || (x==0 && y>0);}
	bool operator != (const point& b) const {return x!=b.x || y!=b.y;}
	bool operator == (const point& b) const {return x==b.x && y==b.y;}
	point operator + (const point& b) const {return point(x+b.x,y+b.y);}
	point operator - (const point& b) const {return point(x-b.x,y-b.y);}
	long long operator * (const point& b) const {return x*1ll*b.y-y*1ll*b.x;}
	bool operator < (const point& b) const {return (dir()==b.dir())?dir():((*this)*b>0);}
};
struct hasher{unsigned operator ()(point x)const{return (hash<int>()(x.x)<<2)^hash<int>()(x.y);}};
ostream& operator << (ostream& out,point p){return out<<"("<<p.x<<","<<p.y<<")";}
unordered_map<point,unordered_map<long long,vector<point>>,hasher> mp;
vector<point> original;
int n;
int main()
{
	cin>>n;
	for(int i=1,x,y;i<=n;i++)	cin>>x>>y,original.emplace_back(x,y);
	for(point x:original)
		for(point y:original)
			if(x!=y)
//				cout<<x+y<<": "<<y-x<<endl,
				mp[x+y][(y-x).dis()].push_back(y-x);
	long long ans=0;
	for(auto& it:mp) for(auto& it2:it.second)
	{
		vector<point>& vec=it2.second;
		sort(vec.begin(),vec.end());
//		cout<<it.first<<": ";
//		for(auto p:vec)	cout<<p<<" ";
//		cout<<endl;
		for(int i=0,j=1;i<vec.size();i++)
		{
			while(vec[(j+1)%vec.size()]*vec[i]>vec[j]*vec[i])	(++j)%=vec.size();
//			cout<<vec[j]<<"*"<<vec[i]<<"="<<vec[j]*vec[i]<<endl;
			ans=max(ans,vec[j]*vec[i]);
			if(i==j)	j++;
		}
	}
	cout<<ans/2<<endl;
}

回复

6 条回复,欢迎继续交流。

正在加载回复...