fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. struct point:pair<int,int>
  6. {
  7.     point(int x = 0, int y = 0)
  8.     {
  9.         first = x, second = y;
  10.     }
  11.  
  12.     int Manhattan_dist(const point& p) const
  13.     {
  14.         return abs(first-p.first)+abs(second-p.second);
  15.     }
  16.  
  17.     friend istream& operator >> (istream& in, point& p)
  18.     {
  19.         return in >> p.first >> p.second;
  20.     }
  21.  
  22.     friend ostream& operator << (ostream& out, const point& p)
  23.     {
  24.         return out << p.first << ' ' << p.second;
  25.     }
  26. };
  27.  
  28. struct points:set<point>
  29. {
  30.     void connect(const point& s, const point& t)
  31.     {
  32.         int x = s.first, y = s.second, 
  33.         	u = t.first, v = t.second;
  34.  
  35.         for(int z = x+1; z <= u; x = z++) // move right
  36.             emplace(z,y);
  37.  
  38.         for(int z = y+1; z < v; y = z++) // move up 
  39.             emplace(x,z);
  40.  
  41.         for(int z = y-1; z > v; y = z--) // move down
  42.             emplace(x,z);
  43.  
  44.         insert(t);
  45.     }
  46.  
  47.     points(int n)
  48.     {
  49.         vector<point> p(n);
  50.  
  51.         for(auto&q:p)
  52.             cin >> q;
  53.  
  54.         sort(p.begin(),p.end()), insert(p[0]), connect(p[0],p[1]);
  55.  
  56.         for(int i = 2; i < n; i++)
  57.         {
  58.             point src; int d_min = INT_MAX; bool connected = false;
  59.  
  60.             for(auto q:*this)
  61.                 if (q == p[i])
  62.                 {
  63.                     connected = true; break;
  64.                 }
  65.                 else
  66.                 {
  67.                 	int d = q.Manhattan_dist(p[i]);
  68.  
  69.                 	if(d < d_min)
  70.                         src = q, d_min = d;
  71.             	}
  72.  
  73.             if (not connected)
  74.                 connect(src,p[i]);
  75.         }
  76.     }
  77.  
  78.     friend ostream& operator << (ostream& out, const points& s)
  79.     {
  80.         out << s.size();
  81.  
  82.         for(auto p:s)
  83.             out << '\n' << p;
  84.  
  85.         return out;
  86.     }
  87. };
  88.  
  89. int main()
  90. {
  91.     ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  92.  
  93. 	int n; cin >> n; cout << points(n);
  94. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
4
0 0
2 4
4 2
4 4
stdout
copy 
11
0 0
1 0
2 0
2 1
2 2
2 3
2 4
3 2
3 4
4 2
4 4
https://ideone.com/HPTI9d
Connect N
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

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!