#include #pragma GCC optimize("Ofast") #define _GLIBCXX_DEBUG using namespace std; using std::cout; using std::cin; using std::endl; using ll=long long; using ld=long double; ll ILL=2167167167167167167; const int INF=2100000000; const ll mod=998244353; #define rep(i,a) for (ll i=0;i using _pq = priority_queue, greater>; template ll LB(vector &v,T a){return lower_bound(v.begin(),v.end(),a)-v.begin();} template ll UB(vector &v,T a){return upper_bound(v.begin(),v.end(),a)-v.begin();} template bool chmin(T &a,const T &b){if(a>b){a=b;return 1;}else return 0;} template bool chmax(T &a,const T &b){if(a void So(vector &v) {sort(v.begin(),v.end());} template void Sore(vector &v) {sort(v.begin(),v.end(),[](T x,T y){return x>y;});} void yneos(bool a){if(a) cout<<"Yes\n"; else cout<<"No\n";} template void vec_out(vector &p){for(int i=0;i<(int)(p.size());i++){if(i) cout<<" ";cout< a,pair b,pair c){ a.first-=b.first; a.second-=b.second; b.first-=c.first; b.second-=c.second; return (0 &l,pair &r){ if(l.first==0&&r.first==0) return l.second>r.second; if(l.first==0){ return l.second>0||r.first<0; } if(r.first==0){ return !(r.second>0||l.first<0); } if((l.first<0)^(r.first<0)) return l.first>0; return l.first*r.second>t; rep(i,t) solve(); } void solve(){ int N; cin>>N; vector> p(N); rep(i,N) cin>>p[i].first>>p[i].second; vector X(N),Y(N); So(p); rep(i,N) tie(X[i],Y[i])=p[i]; auto f=[&](int a,int b)->ll{ return abs(p[a].first*p[b].second-p[a].second*p[b].first); }; if(N<=4000){ ll ans=0; rep(i,N) rep(j,i) chmax(ans,f(i,j)); cout< conv(N*2); int k=0; rep(i,N){ while(k>1&&det(p[conv[k-2]],p[conv[k-1]],p[i])){ k--; } conv[k]=i; k++; } int t=k; for(int i=N-2;i>=0;i--){ while(k>t&&det(p[conv[k-2]],p[conv[k-1]],p[conv[i]])){ k--; } conv[k]=i; k++; } conv.resize(k); int x=0; vector order(N*2+k); rep(i,N*2+k) order[i]=i; auto sub_p=[](pair a,pair b)->pair{ return {a.first-b.first,a.second-b.second}; }; sort(all(order),[&](int l,int r){ pair L,R; if(l re; rep(i,N*4+k*2){ int v=order[i%(N*2+k)]; if(v