Advertisement
Anon2005

woop

Apr 1st, 2019
178
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.99 KB | None | 0 0
  1. #include <fstream>
  2. #include <vector>
  3. using namespace std;
  4. ifstream in("fenceplan.in");
  5. ofstream out("fenceplan.out");
  6. struct mazan
  7. {
  8.     int x,y,ind;
  9. };
  10. mazan v[109];
  11. int maxlat,minlat,maxjos,minjos;
  12. vector <int> nod[109];
  13. bool marc[109];
  14. void dfs(int n)
  15. {
  16.     marc[n]=1;
  17.     maxlat=max(maxlat,v[n].x);
  18.     minlat=min(minlat,v[n].x);
  19.     minjos=min(minjos,v[n].y);
  20.     maxjos=max(maxjos,v[n].y);
  21.     for(int i=0; i<nod[n].size(); i++)
  22.         if(!marc[nod[n][i]])
  23.             dfs(nod[n][i]);
  24.     return;
  25. }
  26. int main()
  27. {
  28.     int n,m,i,a,b,min1=1000;
  29.     in>>n>>m;
  30.     for(i=1; i<=n; i++)
  31.         in>>v[i].x>>v[i].y;
  32.     for(i=1; i<=m; i++)
  33.     {
  34.         in>>a>>b;
  35.         nod[a].push_back(b);
  36.         nod[b].push_back(a);
  37.     }
  38.     for(i=1; i<=n; i++)
  39.         if(!marc[i])
  40.         {
  41.             maxjos=maxlat=0;
  42.             minjos=minlat=109;
  43.             dfs(i);
  44.             min1=min(min1,2*(maxjos-minjos)+2*(maxlat-minlat));
  45.         }
  46.     out<<min1;
  47.     return 0;
  48. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement