#include #include #include using namespace std; using ll = long long; #include #include ll cross(ll a,ll b,ll c,ll d){ return a * d - b * c; } int ccw(pair a,pair b,pair c) { ll dx = b.first - a.first; ll dy = b.second - a.second; ll ddx = c.first - b.first; ll ddy = c.second - b.second; ll now = cross(dx,dy,ddx,ddy); if(now<0) return -1; if(now>0) return 1; return 0; } long double calc(vector> use) { int n = use.size(); sort(use.begin(),use.end()); if(n==1) return 2; vector> upper,lower; for(int i = 0;i=2){ int m = upper.size(); if(ccw(upper[m-2],upper[m-1],use[i])!=-1) upper.pop_back(); else break; } upper.push_back(use[i]); } for(int i = 0;i=2){ int m = lower.size(); if(ccw(lower[m-2],lower[m-1],use[i])!=1) lower.pop_back(); else break; } lower.push_back(use[i]); } long double ans = 0; reverse(lower.begin(),lower.end()); for(int i = 1;i+1 long double { ll dx = upper[i].first - upper[j].first; ll dy = upper[i].second - upper[j].second; return sqrt(dx*dx+dy*dy); }; for(int i = 0;id(i,ni)) ni = nj; else break; } ans = max(d(i,ni),ans); } return ans + 2; } #include #include int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); int n; cin>>n; vector x(n),y(n); for(int i = 0;i>x[i]>>y[i]; atcoder::dsu uf(n); map,int> memo; for(int i = 0;i100) break; pair want = make_pair(x[i]+ni,y[i]+nj); if(memo.find(want)!=memo.end()) { uf.merge(i,memo[want]); } want = make_pair(x[i]-ni,y[i]+nj); if(memo.find(want)!=memo.end()) { uf.merge(i,memo[want]); } want = make_pair(x[i]-ni,y[i]-nj); if(memo.find(want)!=memo.end()) { uf.merge(i,memo[want]); } want = make_pair(x[i]+ni,y[i]-nj); if(memo.find(want)!=memo.end()) { uf.merge(i,memo[want]); } } } } for(auto&now:uf.groups()){ vector> use; for(int i:now) use.push_back(make_pair(x[i],y[i])); ans = max(ans,calc(use)); } cout<