Advertisement
Guest User

Untitled

a guest
Feb 27th, 2017
55
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.70 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. using namespace std;
  5.  
  6. class Graph {
  7. public:
  8. Graph(int n) {
  9. Table.resize(n);
  10. for (int i = 0; i < n; i++) {
  11. Table[i].resize(n);
  12. }
  13. }
  14. ~Graph() {}
  15.  
  16. void AddEdge(int x, int y) {
  17. Table[x][y] = 1;
  18. Table[y][x] = 1;
  19. }
  20.  
  21. bool Path() {
  22. vector<bool> IsVisited;
  23. IsVisited.resize(Table.size());
  24.  
  25. queue<int> q;
  26. q.push(Table.size() - 2);
  27. IsVisited[Table.size()-2] = 1;
  28.  
  29. while (!q.empty()) {
  30. int tmp = q.front();
  31. q.pop();
  32. for (int i = 0; i < Table.size(); i++) {
  33. if (Table[tmp][i] == 1) {
  34. if (!IsVisited[i]) {
  35. if (i == Table.size() - 1) {
  36. return false;
  37. }
  38. q.push(i);
  39. IsVisited[i] = true;
  40. }
  41. }
  42. }
  43.  
  44. }
  45. return true;;
  46. }
  47.  
  48. private:
  49. vector<vector<int>> Table;
  50. };
  51.  
  52.  
  53. int main() {
  54. int XL = 0; int XR = 0;
  55. cin >> XL; cin >> XR;
  56.  
  57. int R = 0;
  58. cin >> R;
  59.  
  60. int N = 0;
  61. cin >> N;
  62.  
  63. vector<pair<int, int>> Verticles;
  64. for (int i = 0; i < N; i++) {
  65. int x = 0; int y = 0;
  66. cin >> x; cin >> y;
  67.  
  68. pair<int, int> a;
  69. a.first = x;
  70. a.second = y;
  71. Verticles.push_back(a);
  72. }
  73.  
  74. Graph g(N + 2);
  75.  
  76. double r = 48.000;
  77.  
  78. for (int i = 0; i < N; i++) {
  79. int x1 = Verticles[i].first;
  80. int y1 = Verticles[i].second;
  81. for (int j = i + 1; j < N;j++) {
  82. int x2 = Verticles[j].first;
  83. int y2 = Verticles[j].second;
  84. if (abs(x2 - x1)*abs(x2 - x1) + abs(y2 - y1)*abs(y2 - y1) < r * r + R*R) {
  85. g.AddEdge(i, j);
  86. }
  87. }
  88. if (x1 - XL < r+R) {
  89. g.AddEdge(i, N);
  90. }
  91. if (XR - x1 < r+R) {
  92. g.AddEdge(i, N + 1);
  93. }
  94. }
  95. if (g.Path()) {
  96. cout << "Yeas";
  97. }
  98. else
  99. {
  100. cout << "Nope";
  101. }
  102. system("pause");
  103. return 0;
  104. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement