Advertisement
MystMe

Untitled

Feb 27th, 2017
72
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.86 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. while(!q.empty()){
  28. int tmp = q.front(); q.pop();
  29. if(!IsVisited[tmp]){
  30. if(tmp == Table.size()-1){
  31. return true;
  32. }
  33. q.push(tmp);
  34. IsVisited[tmp] = true;
  35. }
  36. }
  37. return false;
  38. }
  39.  
  40. private:
  41. vector<vector<int>> Table;
  42. };
  43.  
  44.  
  45. int main() {
  46. int XL = 0; int XR = 0;
  47. cin >> XL; cin >> XR;
  48.  
  49. int R = 0;
  50. cin >> R;
  51.  
  52. int N = 0;
  53. cin >> N;
  54.  
  55. vector<pair<int,int>> Verticles;
  56. for(int i = 0;i < N;i++){
  57. int x = 0; int y = 0;
  58. cin >> x; cin >> y;
  59.  
  60. pair<int,int> a;
  61. a.first = x;
  62. a.second = y;
  63. Verticles.push_back(a);
  64. }
  65.  
  66. Graph g(N+2);
  67.  
  68. int r = 10;
  69.  
  70. for(int i = 0; i < N; i++){
  71. int x1 = Verticles[i].first;
  72. int y1 = Verticles[i].second;
  73. for(int j = i+1; j < N; i++){
  74. int x2 = Verticles[j].first;
  75. int y2 = Verticles[j].second;
  76. if((x2-x1)*(x2-x1) + (y2-y1)*(y2-y1) < r * r){
  77. g.AddEdge(i,j);
  78. }
  79. }
  80. if(x1-XL < r){
  81. g.AddEdge(i,N);
  82. }
  83. if(x1-XR < r){
  84. g.AddEdge(i, N+1);
  85. }
  86. }
  87. if(g.Path()){
  88. cout << "Yeas";
  89. }
  90. else
  91. {
  92. cout << "Nope";
  93. }
  94. return 0;
  95. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement