Advertisement
Guest User

Untitled

a guest
Oct 23rd, 2019
73
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.28 KB | None | 0 0
  1. //Froggy Ford - NEERC 2015
  2. //https://codeforces.com/gym/100851
  3. #include <cstdio>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. #define FILENAME "froggy"
  9.  
  10. double dist[1234][1234];
  11. int x[1234], y[1234];
  12. double u[2][1234];
  13. double d[1234], res[1234];
  14.  
  15. int main() {
  16.   freopen(FILENAME ".in", "r", stdin);
  17.   freopen(FILENAME ".out", "w", stdout);
  18.   int w, n;
  19.   scanf("%d %d", &w, &n);
  20.   for (int i = 0; i < n; i++) {
  21.     scanf("%d %d", x + i, y + i);
  22.   }
  23.   for (int i = 0; i < n + 2; i++) {
  24.     for (int j = 0; j < n + 2; j++) {
  25.       if (i == j) {
  26.         dist[i][j] = 0;
  27.         continue;
  28.       }
  29.       if (i >= n && j >= n) {
  30.         dist[i][j] = w;
  31.         continue;
  32.       }
  33.       if (i >= n) {
  34.         dist[i][j] = (i == n ? x[j] : w - x[j]);
  35.         continue;
  36.       }
  37.       if (j >= n) {
  38.         dist[i][j] = (j == n ? x[i] : w - x[i]);
  39.         continue;
  40.       }
  41.       dist[i][j] = sqrt((x[i] - x[j]) * 1.0 * (x[i] - x[j]) + (y[i] - y[j]) * 1.0 * (y[i] - y[j]));
  42.     }
  43.   }
  44.   double ans = 1e30, ax = -1, ay = -1;
  45.   for (int start = n; start < n + 2; start++) {
  46.     for (int i = 0; i < n + 2; i++) {
  47.       d[i] = 1e30;
  48.       res[i] = 1e30;
  49.     }
  50.     d[start] = 0;
  51.     double mx = 0;
  52.     for (int it = 0; it < n + 2; it++) {
  53.       int best = -1;
  54.       for (int i = 0; i < n + 2; i++) {
  55.         if (res[i] > 1e29 && (best == -1 || d[i] < d[best])) {
  56.           best = i;
  57.         }
  58.       }
  59.       mx = max(mx, d[best]);
  60.       res[best] = mx;
  61.       for (int j = 0; j < n + 2; j++) {
  62.         d[j] = min(d[j], dist[best][j]);
  63.       }
  64.     }
  65.     for (int i = 0; i < n + 2; i++) {
  66.       u[start - n][i] = res[i];
  67.     }
  68.   }
  69.   for (int i = 0; i < n + 2; i++) {
  70.     for (int j = 0; j < n + 2; j++) {
  71.       double cur = max(dist[i][j] / 2, max(u[0][i], u[1][j]));
  72.       if (cur < ans) {
  73.         ans = cur;
  74.         if (i == n && j == n + 1) {
  75.           ax = 0.5 * w;
  76.           ay = 0.0;
  77.         }
  78.         if (i < n && j < n) {
  79.           ax = 0.5 * (x[i] + x[j]);
  80.           ay = 0.5 * (y[i] + y[j]);
  81.         }
  82.         if (i == n && j < n) {
  83.           ax = 0.5 * x[j];
  84.           ay = y[j];
  85.         }
  86.         if (i < n && j == n + 1) {
  87.           ax = 0.5 * (w + x[i]);
  88.           ay = y[i];
  89.         }
  90.       }
  91.     }
  92.   }
  93.   printf("%.17f %.17f\n", ax, ay);
  94.   return 0;
  95. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement