fork(1) download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct P {
  5.     int x,y;
  6.     bool operator==(const P& o) const { return x==o.x && y==o.y; }
  7. };
  8. struct H {
  9.     size_t operator()(P const& p) const { return (uint64_t)(p.x+100003)*200003u ^ (uint64_t)(p.y+100003); }
  10. };
  11.  
  12. long long sum_abs_to(const vector<int>& a, int v){
  13.     long long s=0;
  14.     for(int z:a) s+= llabs((long long)z - v);
  15.     return s;
  16. }
  17.  
  18. int main(){
  19.     ios::sync_with_stdio(false);
  20.     cin.tie(nullptr);
  21.     int T;
  22.     if(!(cin>>T)) return 0;
  23.     const int L=-10000, R=10000;
  24.     while(T--){
  25.         int n; cin>>n;
  26.         vector<int> xs(n), ys(n);
  27.         vector<P> pts(n);
  28.         unordered_set<P,H> st;
  29.         st.reserve(n*2+1);
  30.         for(int i=0;i<n;i++){
  31.             int x,y; cin>>x>>y;
  32.             xs[i]=x; ys[i]=y;
  33.             pts[i]={x,y};
  34.             st.insert({x,y});
  35.         }
  36.         sort(xs.begin(),xs.end());
  37.         sort(ys.begin(),ys.end());
  38.         long long Sx,Sy;
  39.         int xL,xR,yL,yR,xm,ym;
  40.         if(n%2){
  41.             xm = xs[n/2];
  42.             ym = ys[n/2];
  43.             Sx = sum_abs_to(xs,xm);
  44.             Sy = sum_abs_to(ys,ym);
  45.             long long S = Sx+Sy;
  46.             long long K = 1;
  47.             if(st.count({xm,ym})){
  48.                 S += 1;
  49.                 K = 0;
  50.                 if(xm-1>=L && !st.count({xm-1,ym})) K++;
  51.                 if(xm+1<=R && !st.count({xm+1,ym})) K++;
  52.                 if(ym-1>=L && !st.count({xm,ym-1})) K++;
  53.                 if(ym+1<=R && !st.count({xm,ym+1})) K++;
  54.             }
  55.             cout<<S<<" "<<K<<"\n";
  56.         }else{
  57.             xL = xs[n/2 - 1]; xR = xs[n/2];
  58.             yL = ys[n/2 - 1]; yR = ys[n/2];
  59.             Sx = sum_abs_to(xs,xL);
  60.             Sy = sum_abs_to(ys,yL);
  61.             long long S = Sx+Sy;
  62.             long long w = (long long)xR - xL + 1;
  63.             long long h = (long long)yR - yL + 1;
  64.             long long K0 = w*h;
  65.             long long inside = 0;
  66.             for(auto &p: pts){
  67.                 if(p.x>=xL && p.x<=xR && p.y>=yL && p.y<=yR) inside++;
  68.             }
  69.             if(inside < K0){
  70.                 cout<<S<<" "<<(K0 - inside)<<"\n";
  71.             }else{
  72.                 long long K = 0;
  73.                 S += 1;
  74.                 for(int Y=yL; Y<=yR; ++Y){
  75.                     if(xL-1>=L && !st.count({xL-1,Y})) ++K;
  76.                     if(xR+1<=R && !st.count({xR+1,Y})) ++K;
  77.                 }
  78.                 for(int X=xL; X<=xR; ++X){
  79.                     if(yL-1>=L && !st.count({X,yL-1})) ++K;
  80.                     if(yR+1<=R && !st.count({X,yR+1})) ++K;
  81.                 }
  82.                 cout<<S<<" "<<K<<"\n";
  83.             }
  84.         }
  85.     }
  86.     return 0;
  87. }
  88.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin 
1
2
0 1
1 0
stdout 
2 2
https://ideone.com/LUWq0N
language:
C++14 (clang 8.0)
created:
9 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!