Advertisement
Guest User

Untitled

a guest
Nov 25th, 2017
62
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.90 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define FOR(i,a,b) for (int i = (a); i < (b); i++)
  5. #define RFOR(i,b,a) for (int i = (b)-1; i >= (a); i--)
  6. #define ITER(it,a) for (__typeof(a.begin()) it = a.begin(); it != a.end(); it++)
  7. #define FILL(a,value) memset(a, value, sizeof(a))
  8.  
  9. #define SZ(a) (int)a.size()
  10. #define ALL(a) a.begin(), a.end()
  11. #define PB push_back
  12. #define MP make_pair
  13.  
  14. typedef long long LL;
  15. typedef vector<int> VI;
  16. typedef pair<int, int> PII;
  17.  
  18. const double PI = acos(-1.0);
  19. const int INF = 1000 * 1000 * 1000 + 7;
  20. const LL LINF = INF * (LL) INF;
  21.  
  22. const int MAX = 111;
  23.  
  24. int X[MAX], Y[MAX];
  25. int DX[MAX], DY[MAX];
  26. int n, m, p;
  27.  
  28.  
  29.  
  30. pair<double, int> E[MAX * MAX * MAX];
  31.  
  32.  
  33. double timeTo(double a, double b)
  34. {
  35. double ans = b - a;
  36. if (ans < 0)ans += 2 * n;
  37. return ans;
  38. }s
  39.  
  40. bool ok(double x)
  41. {
  42. int sz = 0;
  43. FOR(i, 0, p)
  44. {
  45. if (DX[i] == 0)
  46. {
  47. int id = i + 1;
  48. E[sz++] = MP(0, id);
  49. }
  50. else if (DX[i] > 0)
  51. {
  52. double cur = .0;
  53. double pos = X[i];
  54. while (cur < 3 * n)
  55. {
  56. if (timeTo(x) < timeTo(2 * n - x))
  57. {
  58. pos = x;
  59. cur += timeTo(x);
  60. E[sz++] = MP(cur, DX[i] > 0 ? i + 1 : -(i+1));
  61. }
  62. }
  63. }
  64.  
  65. }
  66. }
  67.  
  68. double solve()
  69. {
  70. double l = .0;
  71. double r = n;
  72.  
  73. FOR(i, 0, 60)
  74. {
  75. double m = (l + r) * .5;
  76. if (ok(m)) l = m;
  77. else r = m;
  78. }
  79. return l * m;
  80. }
  81.  
  82. int main()
  83. {
  84. //freopen("in.txt", "r", stdin);
  85. //ios::sync_with_stdio(false); cin.tie(0);
  86. scanf("%d%d", &n, &m);
  87. scanf("%d", &p);
  88. FOR(i, 0, p)
  89. {
  90. scanf("%d%d%d%d", X + i, Y + i, DX + i, DY + i);
  91. }
  92. double ans = 1e100;
  93.  
  94.  
  95. FOR(it, 0, 2)
  96. {
  97.  
  98. FOR(it2, 0, 2)
  99. {
  100.  
  101. ans = min(ans, solve());
  102.  
  103. FOR(i, 0, p)
  104. {
  105. swap(X[i], Y[i]);
  106. swap(DX[i], DY[i]);
  107. }
  108. }
  109.  
  110. FOR(i, 0, p)
  111. {
  112. X[i] = n - X[i];
  113. DX[i] = -DX[i];
  114. }
  115. }
  116.  
  117.  
  118. ans = min(ans, solve());
  119. printf("%.7f", ans);
  120.  
  121.  
  122. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement