Advertisement
Guest User

Untitled

a guest
Nov 16th, 2018
79
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.53 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. ifstream fin("date.in");
  4. ofstream fout("date.out");
  5. int n, m, i, j, k;
  6. bool ok = 0;
  7. struct cladire
  8. {
  9. int x, y;
  10. int arie;
  11. };
  12. bool cmp(cladire a, cladire b);
  13. void initializare(int mat[1001][1001]);
  14. int dfs1(int x, int y, int height);
  15. void dfs2(int x, int y, int height);
  16. long double xsum = 0, ysum = 0, points = 0;
  17. void afisare(int mat[1001][1001]);
  18. int a[1001][1001];
  19. int verif[1001][1001];
  20. vector<cladire> v;
  21. int main()
  22. {
  23. fin>>n>>m;
  24. for(i=1; i<=n; i++)
  25. for(j=1; j<=m; j++)
  26. fin >> a[i][j];
  27. for(i=1; i<=n; i++)
  28. for(j=1; j<=m; j++)
  29. if(a[i][j] && !verif[i][j])
  30. v.push_back({i, j, dfs1(i, j, a[i][j])});
  31. sort(v.begin(), v.end(), cmp);
  32. fin >> k;
  33. for(int l=1; l<=k; l++)
  34. {
  35. int id1, id2;
  36. long double xcentre1, ycentre1, xcentre2, ycentre2;
  37. fin >> id1 >> id2;
  38. initializare(verif);
  39. //centre1
  40. xsum = 0, ysum = 0, points = 0;
  41. dfs2(v[id1].x, v[id1].y, a[v[id1].x][v[id1].y]);
  42. xcentre1 = (long double)(xsum/points);
  43. ycentre1 = (long double)(ysum/points);
  44. //centre2
  45. xsum = 0, ysum = 0, points = 0;
  46. dfs2(v[id2].x, v[id2].y, a[v[id2].x][v[id2].y]);
  47. xcentre2 = (long double)(xsum/points);
  48. ycentre2 = (long double)(ysum/points);
  49. cout << xcentre1 << ' ' << ycentre1 << '\n';
  50. cout << xcentre2 << ' ' << ycentre2 << '\n';
  51. cout << '\n';
  52. }
  53.  
  54. return 0;
  55. }
  56. void dfs2(int x, int y, int height)
  57. {
  58. if(a[x][y] == 0 or a[x][y]!=height or verif[x][y])
  59. return ;
  60. else
  61. {
  62. verif[x][y] = 1;
  63. xsum+=x;
  64. ysum+=y;
  65. points++;
  66. dfs2(x+1, y, height);
  67. dfs2(x, y+1, height);
  68. dfs2(x, y-1, height);
  69. dfs2(x-1, y, height);
  70. }
  71. }
  72. bool cmp(cladire a, cladire b)
  73. {
  74. return (a.arie < b.arie);
  75. }
  76. void afisare(int mat[1001][1001])
  77. {
  78. for(int i=1; i<=n; i++)
  79. {
  80. for(j=1; j<=m; j++)
  81. cout << mat[i][j] << ' ';
  82. cout << '\n';
  83. }
  84. }
  85. void initializare(int mat[1001][1001])
  86. {
  87. for(int i=1; i<=n; i++)
  88. for(int j=1; j<=m; j++)
  89. mat[i][j] = 0;
  90. }
  91. int dfs1(int x, int y, int height)
  92. {
  93. if(a[x][y] == 0 or a[x][y] != height or verif[x][y])
  94. return 0;
  95. else
  96. {
  97. verif[x][y] = 1;
  98. int sol=1+dfs1(x+1, y, height)+ dfs1(x, y+1, height)+ dfs1(x-1, y, height)+ dfs1(x, y-1, height);
  99. return sol;
  100. }
  101. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement