Advertisement
Guest User

Untitled

a guest
Sep 23rd, 2017
82
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.60 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. typedef vector<int> vi;
  7. typedef pair<int, int> pii;
  8.  
  9. #define X first
  10. #define Y second
  11. #define mk make_pair
  12. #define inb push_back
  13. #define all(v) v.begin(), v.end()
  14.  
  15. const double eps = 1e-6;
  16. const int BP = 100;
  17.  
  18. bool eq(double a, double b)
  19. {
  20. return abs(a - b) <= eps;
  21. }
  22.  
  23. double dist(pair<double, double> a, pair<double, double> b)
  24. {
  25. return (a.X - b.X) * (a.X - b.X) + (a.Y - b.Y) * (a.Y - b.Y);
  26. }
  27.  
  28. int main()
  29. {
  30. //freopen("input.txt", "r", stdin);
  31. //freopen("output.txt", "w", stdout);
  32. int n;
  33. double w;
  34. cin >> w >> n;
  35. if (n == 0) cout << w / 2 << ' ' << 0, exit(0);
  36. vector<pair<double, double> > a(n);
  37. for(int i = 0; i < n; ++i)
  38. cin >> a[i].X >> a[i].Y;
  39. vector<vector<double> > dp(n, vector<double>(2));
  40. for(int i = 0; i < n; ++i)
  41. {
  42. dp[i][0] = a[i].X * a[i].X;
  43. dp[i][1] = a[i].X * a[i].X / 4;
  44. }
  45. vector<vector<bool> > us(n, vector<bool>(2));
  46. vector<vector<pii> > p(n, vector<pii>(2));
  47. for(int i = 0; i < n; ++i) p[i][0].X = p[i][1].X = -1;
  48. double ans = w * w / 4;
  49. int g, h;
  50. double c = w / 2, d = 0;
  51. for(int q = 0; q < n * 2; ++q)
  52. {
  53. double mn = 2e9;
  54. int i, l;
  55. for(int j = 0; j < n; ++j)
  56. for(int k = 0; k < 2; ++k)
  57. if (!us[j][k] && dp[j][k] < mn)
  58. mn = dp[j][k], i = j, l = k;
  59. us[i][l] = 1;
  60. if (!l && max(dp[i][l], (w - a[i].X) * (w - a[i].X) / 4) < ans)
  61. ans = max(dp[i][l], (w - a[i].X) * (w - a[i].X) / 4), g = i, h = l;
  62. else if (max(dp[i][l], (w - a[i].X) * (w - a[i].X)) < ans)
  63. ans = max(dp[i][l], (w - a[i].X) * (w - a[i].X)), g = i, h = l;
  64. for(int j = 0; j < n; ++j)
  65. {
  66. if (!l)
  67. {
  68. if (max(dp[i][l], dist(a[i], a[j])) < dp[j][0])
  69. dp[j][0] = max(dp[i][l], dist(a[i], a[j])), p[j][0] = { i, 0 };
  70. if (max(dp[i][l], dist(a[i], a[j]) / 4) < dp[j][1])
  71. dp[j][1] = max(dp[i][l], dist(a[i], a[j]) / 4), p[j][1] = { i, 0 };
  72. }
  73. else
  74. {
  75. if (max(dp[i][l], dist(a[i], a[j])) < dp[j][1])
  76. dp[j][1] = max(dp[i][l], dist(a[i], a[j])), p[j][1] = { i, 1 };
  77. }
  78. }
  79. }
  80. int l = g, r = h;
  81. while(p[l][r].X != -1)
  82. {
  83. g = p[l][r].X, h = p[l][r].Y;
  84. if (h != r) c = (a[l].X + a[g].X) / 2, d = (a[l].Y + a[g].Y) / 2;
  85. l = g, r = h;
  86. }
  87. cout << c << ' ' << d;
  88. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement