fork(1) download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct P{ long long x,y; };
  5. struct PH{
  6.     size_t operator()(P const& p) const {
  7.         return std::hash<long long>()(p.x*1000003LL ^ (p.y+0x9e3779b97f4a7c15ULL));
  8.     }
  9. };
  10. struct PE{ 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(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,PH,PE> S; S.reserve(n*2+1);
  24.         for(int i=0;i<n;i++){
  25.             long long x,y; cin>>x>>y; xs[i]=x; ys[i]=y; S.insert({x,y});
  26.         }
  27.         vector<long long> sx=xs, sy=ys;
  28.         sort(sx.begin(),sx.end());
  29.         sort(sy.begin(),sy.end());
  30.  
  31.         if(n%2==1){
  32.             long long xm=sx[n/2], ym=sy[n/2];
  33.             long long best = sum_abs_axis(xs,xm) + sum_abs_axis(ys,ym);
  34.             if(!S.count({xm,ym})){
  35.                 cout<<best<<" "<<1<<"\n";
  36.             }else{
  37.                 long long k=0;
  38.                 if(!S.count({xm+1,ym})) ++k;
  39.                 if(!S.count({xm-1,ym})) ++k;
  40.                 if(!S.count({xm,ym+1})) ++k;
  41.                 if(!S.count({xm,ym-1})) ++k;
  42.                 cout<<best+1<<" "<<k<<"\n";
  43.             }
  44.         }else{
  45.             long long xL=sx[n/2-1], xR=sx[n/2];
  46.             long long yL=sy[n/2-1], yR=sy[n/2];
  47.             long long best = sum_abs_axis(xs,xL) + sum_abs_axis(ys,yL);
  48.  
  49.             long long w = xR - xL + 1;
  50.             long long h = yR - yL + 1;
  51.             long long k0 = w*h;
  52.  
  53.             long long insideUnique = 0;
  54.             for(auto const& p: S){
  55.                 if(p.x>=xL && p.x<=xR && p.y>=yL && p.y<=yR) ++insideUnique;
  56.             }
  57.             long long freeInside = k0 - insideUnique;
  58.  
  59.             if(freeInside>0){
  60.                 cout<<best<<" "<<freeInside<<"\n";
  61.             }else{
  62.                 long long k=0;
  63.                 for(long long y=yL; y<=yR; ++y){
  64.                     if(!S.count({xL-1,y})) ++k;
  65.                     if(!S.count({xR+1,y})) ++k;
  66.                 }
  67.                 for(long long x=xL; x<=xR; ++x){
  68.                     if(!S.count({x,yL-1})) ++k;
  69.                     if(!S.count({x,yR+1})) ++k;
  70.                 }
  71.                 cout<<best+1<<" "<<k<<"\n";
  72.             }
  73.         }
  74.     }
  75.     return 0;
  76. }
  77.  
Success #stdin #stdout 0s 5324KB
comments (?)
stdin 
1
2
0 1
1 0
stdout 
2 2
https://ideone.com/34SHhh
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!