Advertisement
wurdalak007

Untitled

Feb 27th, 2018
249
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 5.16 KB | None | 0 0
  1. // Единственный способ попасть в зал круглых столов - пройти через колонный коридор. Стены коридора
  2. // изображаются на карте прямыми линиями, которые параллельны оси OY системы координат.
  3. // Вход в коридор находится снизу, а выход из коридора в зал - сверху. В коридоре есть цилиндрические
  4. // (на карте круглы) колонны одинакового радиуса R.
  5. // Разработайте алгоритм, который по информации о размерах коридора и размещения колонн определяет диаметр
  6. // наибольшего из круглых столов, который можно пронести через такой коридор, сохраняя поверхность горизонтальной.
  7.  
  8. #include <iostream>
  9. #include <vector>
  10. #include <set>
  11. #include <algorithm>
  12. #include <cmath>
  13. #include <cstdio>
  14. using namespace std;
  15.  
  16. class MyGraph {
  17. public:
  18. // конструктор
  19. MyGraph();
  20. // деструктор
  21. ~MyGraph();
  22. // считываем все входные данные
  23. void ReadData();
  24. // строим граф
  25. void BuildGraph();
  26. // dfs для поиска компонент связности
  27. void DfsFindSCC(int v, vector <int> &component);
  28. // поиск компонент сильной связности
  29. void FindSCC();
  30. // проверка, можем ли мы пронести стол
  31. bool CheckComponents();
  32. // бинарный поиск по ответу (диаметру стола)
  33. void BinSearch();
  34.  
  35. private:
  36. // левая стенка
  37. int xL;
  38. // правая стенка
  39. int xR;
  40. // радиус колонн
  41. int r;
  42. // кол-во колонн
  43. int n;
  44. // набор всех колонн и их проекций
  45. vector <pair <int, int> > vertex;
  46. // диаметр стола
  47. double D;
  48. // граф
  49. vector <vector <int> > g;
  50. // массив посещенных вершин
  51. vector <bool> used;
  52. // массив, в котором хранятся компоненты сильной связности
  53. vector <vector <int> > components;
  54. // кол-во вершин
  55. int V;
  56. };
  57.  
  58. MyGraph::MyGraph() {
  59. }
  60.  
  61. MyGraph::~MyGraph() {
  62. g.clear();
  63. used.clear();
  64. components.clear();
  65. vertex.clear();
  66. }
  67.  
  68. void MyGraph::ReadData() {
  69. set<int> proj;
  70. cin >> xL >> xR;
  71. cin >> r;
  72. xL -= r;
  73. xR += r;
  74. cin >> n;
  75.  
  76. for( int i = 0; i < n; i++ ) {
  77. int x, y;
  78. cin >> x >> y;
  79. vertex.push_back( make_pair(x, y) );
  80.  
  81. if( proj.count(y) == 0 ) {
  82. proj.insert(y);
  83. vertex.push_back( make_pair(xL, y) );
  84. vertex.push_back( make_pair(xR, y) );
  85. }
  86. }
  87.  
  88. V = vertex.size();
  89. }
  90.  
  91. void MyGraph::BuildGraph() {
  92. g.assign( V, vector <int>() );
  93. for( int i = 0; i < V; i++ )
  94. for( int j = 0; j < V; j++ ) {
  95. int dist = (vertex[i].first - vertex[j].first) * (vertex[i].first - vertex[j].first);
  96. dist += (vertex[i].second - vertex[j].second) * (vertex[i].second - vertex[j].second);
  97. if( i != j && dist < D*D ) {
  98. g[i].push_back(j);
  99. }
  100. }
  101. }
  102.  
  103. void MyGraph::DfsFindSCC(int v, vector <int> &component) {
  104. used[v] = true;
  105. component.push_back(v);
  106. for( int i = 0; i < g[v].size(); i++ ) {
  107. if( !used[g[v][i]] ) {
  108. DfsFindSCC( g[v][i], component );
  109. }
  110. }
  111. }
  112.  
  113. void MyGraph::FindSCC() {
  114. components.clear();
  115. used.assign(V, false);
  116. for( int i = 0; i < V; i++ ) {
  117. int v = i;
  118. if( !used[v] ) {
  119. vector <int> component;
  120. DfsFindSCC(v, component);
  121. components.push_back(component);
  122. }
  123. }
  124. }
  125.  
  126. bool MyGraph::CheckComponents() {
  127. bool answer = true;
  128. for( int i = 0; i < components.size(); i++ ) {
  129. bool on_right_wall = false;
  130. bool on_left_wall = false;
  131. for( int j = 0; j < components[i].size(); j++ ) {
  132. int v = components[i][j];
  133. if( vertex[v].first == xL ) {
  134. on_left_wall = true;
  135. }
  136. if( vertex[v].first == xR ) {
  137. on_right_wall = true;
  138. }
  139. }
  140. if( on_right_wall && on_left_wall ) {
  141. answer = false;
  142. }
  143. }
  144. return answer;
  145. }
  146.  
  147. void MyGraph::BinSearch() {
  148. double left = 0.000;
  149. double right = xR - xL;
  150. while( right - left > 0.0001 ) {
  151. double m = (left + right) / 2;
  152. D = m;
  153. BuildGraph();
  154. FindSCC();
  155. bool ans = CheckComponents();
  156. if( ans ) {
  157. left = m;
  158. } else {
  159. right = m;
  160. }
  161. }
  162. cout << fixed;
  163. cout.precision(3);
  164. cout << abs(D - 2*r);
  165. }
  166.  
  167. int main() {
  168. MyGraph g;
  169. g.ReadData();
  170. g.BinSearch();
  171. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement