fork download
copy 
  1. /*
  2. 초속 v미터
  3. 이동 시에는 m분동안 생존 가능
  4. 이동가능한 거리 = 60.0*v*m
  5. dfs 또는 bfs로 이동가능한 거리만 탐색
  6. v=1, m=1이면 1초에 1미터 이동, 1분엔 60미터 이동
  7. sqrt를 쓰지 않을 것이므로 제곱된 값으로 계산
  8. */
  9.  
  10. #include <iostream>
  11. #include <vector>
  12. #include <queue>
  13. #include <sstream>
  14. #include <string>
  15.  
  16. using namespace std;
  17. #define SIZE 1002
  18. int N = 0;
  19. double range = 0;
  20. double arr[SIZE][2];
  21. vector<pair<int, int> > graph[SIZE];
  22.  
  23. int bfs() {
  24.     int count[SIZE];
  25.     queue<pair<int, int> > q;
  26.     for (int i = 0; i < N; i++) {
  27.         count[i] = -1;
  28.     }
  29.  
  30.     q.emplace(0, 0);
  31.     while (!q.empty()) {
  32.         int from = q.front().first;
  33.         int c = q.front().second;
  34.         q.pop();
  35.         if (count[from] <= c && count[from] != -1) {
  36.             continue;
  37.         }
  38.         count[from] = c;
  39.         if (from == 1) {
  40.             continue;
  41.         }
  42.         for (int i = 0; i < graph[from].size(); i++) {
  43.             int to = graph[from][i].first;
  44.             int dist = graph[from][i].second;
  45.             if (dist <= range) {
  46.                 cout << from << ' ' << to << ':' << dist << endl;
  47.  
  48.                 q.emplace(to, c + 1);
  49.             }
  50.         }
  51.     }
  52.     return count[1];
  53. }
  54.  
  55. int main() {
  56.     double V, M;
  57.     cin >> V >> M;
  58.     range = V * M * 60.0;
  59.     range *= range;
  60.  
  61.     string line;
  62.     while (getline(cin, line) && !line.empty()) {
  63.         istringstream output(line);
  64.         output >> arr[N][0] >> arr[N][1];
  65.         // 벙커 간 거리
  66.         for (int to = 0; to < N; to++) {
  67.             double dx = arr[N][0] - arr[to][0];
  68.             double dy = arr[N][1] - arr[to][1];
  69.             double d = dx * dx + dy * dy;
  70.             graph[N].emplace_back(to, d);
  71.             graph[to].emplace_back(N, d);
  72.         }
  73.         N++;
  74.     }
  75.  
  76.     int n = bfs();
  77.     if (n < 0) {
  78.         cout << "No.";
  79.     } else {
  80.         cout << "Yes, visiting " << n << " other holes.";
  81.     }
  82. }
  83.  
  84. /*
  85. 1.416 1
  86. 0 0
  87. 180 180
  88. 60 0
  89. 120 0
  90. 180 60
  91. 180 0
  92. 180 120
  93.  */
  94.  
Success #stdin #stdout 0.01s 5300KB
comments (?)
stdin
copy 
3 1
0.000 0.000
500.000 0.000
179.000 0.000
358.000 0.000
stdout
copy 
Yes, visiting 0 other holes.
https://ideone.com/PYA7BP
language:
C++ (gcc 8.3)
created:
10 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!