Advertisement
Guest User

Untitled

a guest
Feb 22nd, 2017
65
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.69 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <fstream>
  4. #include <vector>
  5. #define pii pair <int, int>
  6. using namespace std;
  7.  
  8. bool liber[1010][1010];
  9. bool cp[1010][1010];
  10. int n, m, ltip, h;
  11.  
  12. vector <pair <pii, pii>> best;
  13. int abest;
  14. vector <pair <pii, pii>> act;
  15.  
  16. void verif(int x, int y)
  17. {
  18. if (!liber[x][y])
  19. return;
  20. int t1(0), t2(0);
  21. int l(0); /// cu cat ma duc in jos
  22. if (cp[x][y])
  23. t1++;
  24. else
  25. t2++;
  26. while (l + 1 < h && x + l + 1 <= n) {
  27. if (!liber[x + l + 1][y])
  28. break;
  29. if (cp[x + l + 1][y])
  30. t1++;
  31. else
  32. t2++;
  33. l++;
  34. }
  35. vector <pii> v;
  36. if (t1 >= ltip && t2 >= ltip)
  37. v.push_back({ x + l, y });
  38. for (int i(1); i < h && y + i <= m; i++) {
  39. int lmin(0);
  40. for (int j(0); j <= l; j++) {
  41. if (!liber[x + j][y + i])
  42. break;
  43. lmin++;
  44. }
  45. while ((l + 1) * (i + 1) > h || l >= lmin) {
  46. for (int j(y); j < y + i; j++) {
  47. if (cp[x + l][j])
  48. t1--;
  49. else
  50. t2--;
  51. }
  52. l--;
  53. }
  54. if (l == -1)
  55. break;
  56. for (int j(0); j <= l; j++) {
  57. if (cp[x + j][y + i])
  58. t1++;
  59. else
  60. t2++;
  61. }
  62.  
  63. if (t1 >= ltip && t2 >= ltip)
  64. v.push_back({ x + l, y + i });
  65. }
  66.  
  67. vector <pii> maxim;
  68. int amax(0);
  69. for (auto i : v) {
  70. if ((i.first - x + 1) * (i.second - y + 1) == amax)
  71. maxim.push_back(i);
  72. if ((i.first - x + 1) * (i.second - y + 1) > amax) {
  73. maxim.clear();
  74. maxim.push_back(i);
  75. amax = (i.first - x + 1) * (i.second - y + 1);
  76. }
  77. }
  78.  
  79. if (maxim.empty())
  80. return;
  81. int q = x * x + y * x * y + 45;
  82. q %= maxim.size();
  83. pii ans = maxim[q];
  84.  
  85. act.push_back({ { x, ans.first }, { y, ans.second } });
  86.  
  87. for (int i(x); i <= ans.first; i++)
  88. for (int j(y); j <= ans.second; j++)
  89. liber[i][j] = 0;
  90. }
  91.  
  92. int main()
  93. {
  94. ifstream in("input.in");
  95. in >> n >> m >> ltip >> h;
  96.  
  97. vector <pii> v;
  98.  
  99. for (int i(1); i <= n; i++) {
  100. for (int j(1); j <= m; j++) {
  101. v.push_back({ i, j });
  102. char c;
  103. in >> c;
  104. cp[i][j] = (c == 'T' ? 1 : 0);
  105. }
  106. }
  107.  
  108. int x(1000);
  109. while (x--) {
  110. random_shuffle(v.begin(), v.end());
  111. act.clear();
  112. for (int i(1); i <= n; i++)
  113. for (int j(1); j <= m; j++)
  114. liber[i][j] = 1;
  115. //verif(1, 3);
  116. //verif(1, 3);
  117. for (pii i : v)
  118. verif(i.first, i.second);
  119.  
  120. int aact(0);
  121. for (auto i : act) {
  122. aact += (i.second.first - i.first.first + 1) *
  123. (i.second.second - i.first.second + 1);
  124. }
  125. int s(act.size());
  126.  
  127. if (aact > abest) {
  128. abest = aact;
  129. best.clear();
  130. best = act;
  131. }
  132. }
  133.  
  134. ofstream out("afisare.out");
  135. out << best.size() << '\n';
  136.  
  137. for (auto i : best) {
  138. out << i.first.first - 1 << ' ' << i.second.first - 1 << ' ';
  139. out << i.first.second - 1 << ' ' << i.second.second - 1 << '\n';
  140. }
  141. return 0;
  142. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement