#include #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #define fi first #define se second #define int long long #define vec vector #define all(m) (m).begin(), (m).end() using namespace std; typedef pair pii; const int inf = 2e18; bool comp1(pii a, pii b){ if(a.fi < b.fi){ return true; } if(a.fi > b.fi) return false; return a.se < b.se; } bool comp2(pii a, pii b){ if(a.se < b.se){ return true; } if(a.se > b.se) return false; return a.fi < b.fi; } int sq(int x){ return x * x; } void solve() { int n; cin>>n; vec x; vec y; for(int i = 0;i>p>>t; x.push_back({p, t}); y.push_back({p, t}); } sort(all(x), comp1); sort(all(y), comp2); int x_f = 0; int x_l = x.size()-1; int y_f = 0; int y_l = y.size()-1; int cnt = n; map used; while(cnt > 4){ pii fx = x[x_f]; while(x_f < x.size() && used[fx]){ x_f++; fx = x[x_f]; } cnt--; used[fx] = 1; x_f++; //if(cnt == 8){ // break; //} pii lx = x[x_l]; while(x_l >=0 && used[lx]){ x_l--; lx = x[x_l]; } cnt --; used[lx] = 1; x_l--; // if(cnt == 8){ // break; //} pii fy = y[y_f]; while(y_f < x.size() && used[fy]){ y_f++; fy = y[y_f]; } cnt--; used[fy] = 1; y_f++; ///if(cnt == 8){ /// break; //} pii ly = y[y_l]; while(y_l >=0 && used[ly]){ y_l--; ly = y[y_l]; } cnt --; used[ly] = 1; y_l--; } vec p; for(int i = x_f;i<=x_l;i++){ pii ty = x[i]; if(!used[ty]){ p.push_back(ty); } } pii p1 = p[0]; pii p2 = p[1]; pii p3 = p[2]; pii p4 = p[3]; // cout << p1.fi << " " << p1.se << "\n"; // cout << p2.fi << " " << p2.se << "\n"; // cout << p3.fi << " " << p3.se << "\n"; // cout << p4.fi << " " << p4.se << "\n"; //for(int i = 0;i