社区讨论
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 条回复,欢迎继续交流。
正在加载回复...