fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct P{ long long x,y; };
  5. struct H{
  6.     size_t operator()(P const& p) const {
  7.         return std::hash<long long>()(p.x ^ (p.y+0x9e3779b97f4a7c15ULL));
  8.     }
  9. };
  10. struct E{ bool operator()(P const& a, P const& b) const { return a.x==b.x && a.y==b.y; } };
  11.  
  12. long long sum_abs_axis(const vector<long long>& a, long long v){
  13.     long long s=0; for(long long z:a) s+= llabs(z-v); return s;
  14. }
  15.  
  16. int main(){
  17.     ios::sync_with_stdio(false);
  18.     cin.tie(nullptr);
  19.     int T; if(!(cin>>T)) return 0;
  20.     while(T--){
  21.         int n; cin>>n;
  22.         vector<long long> xs(n), ys(n);
  23.         unordered_set<P,H,E> seen; seen.reserve(n*2+1);
  24.         for(int i=0;i<n;i++){ cin>>xs[i]>>ys[i]; seen.insert({xs[i],ys[i]}); }
  25.         vector<long long> sx=xs, sy=ys;
  26.         sort(sx.begin(),sx.end());
  27.         sort(sy.begin(),sy.end());
  28.  
  29.         if(n%2==1){
  30.             long long xm=sx[n/2], ym=sy[n/2];
  31.             long long S = sum_abs_axis(xs,xm) + sum_abs_axis(ys,ym);
  32.             if(!seen.count({xm,ym})){
  33.                 cout<<S<<" "<<1<<"\n";
  34.             }else{
  35.                 long long K=0;
  36.                 if(!seen.count({xm+1,ym})) ++K;
  37.                 if(!seen.count({xm-1,ym})) ++K;
  38.                 if(!seen.count({xm,ym+1})) ++K;
  39.                 if(!seen.count({xm,ym-1})) ++K;
  40.                 cout<<S+1<<" "<<K<<"\n";
  41.             }
  42.         }else{
  43.             long long xL=sx[n/2-1], xR=sx[n/2];
  44.             long long yL=sy[n/2-1], yR=sy[n/2];
  45.             long long S = sum_abs_axis(xs,xL) + sum_abs_axis(ys,yL);
  46.  
  47.             long long w = xR - xL + 1;
  48.             long long h = yR - yL + 1;
  49.             long long totalRect = w*h;
  50.  
  51.             long long inside = 0;
  52.             for(auto const& p: seen)
  53.                 if(p.x>=xL && p.x<=xR && p.y>=yL && p.y<=yR) ++inside;
  54.  
  55.             long long freeInside = totalRect - inside;
  56.             if(freeInside>0){
  57.                 cout<<S<<" "<<freeInside<<"\n";
  58.             }else{
  59.                 long long K=0;
  60.                 for(long long y=yL; y<=yR; ++y){
  61.                     if(!seen.count({xL-1,y})) ++K;
  62.                     if(!seen.count({xR+1,y})) ++K;
  63.                 }
  64.                 for(long long x=xL; x<=xR; ++x){
  65.                     if(!seen.count({x,yL-1})) ++K;
  66.                     if(!seen.count({x,yR+1})) ++K;
  67.                 }
  68.                 cout<<S+1<<" "<<K<<"\n";
  69.             }
  70.         }
  71.     }
  72.     return 0;
  73. }
  74.  
Success #stdin #stdout 0.01s 5308KB
comments (?)
stdin 
1
2
0 1
1 0
stdout 
2 2
https://ideone.com/04LZWg
language:
C++14 (clang 8.0)
created:
8 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!