Advertisement
Guest User

Untitled

a guest
Jan 21st, 2018
77
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.06 KB | None | 0 0
  1. #include <iostream>
  2. #include <sstream>
  3. #include <iomanip>
  4. #include <cstdio>
  5. #include <cstdlib>
  6. #include <cmath>
  7. #include <cctype>
  8. #include <cstring>
  9. #include <vector>
  10. #include <list>
  11. #include <queue>
  12. #include <deque>
  13. #include <stack>
  14. #include <map>
  15. #include <set>
  16. #include <algorithm>
  17. #include <iterator>
  18. #include <bitset>
  19. #include <ctime>
  20. #include <complex>
  21.  
  22. using namespace std;
  23.  
  24. #define FOR(i,a,b) for (int i = (a); i < (b); i++)
  25. #define RFOR(i,b,a) for (int i = (b)-1; i >= (a); i--)
  26. #define ITER(it,a) for (__typeof(a.begin()) it = a.begin(); it != a.end(); it++)
  27. #define FILL(a,value) memset(a, value, sizeof(a))
  28.  
  29. #define SZ(a) (int)a.size()
  30. #define ALL(a) a.begin(), a.end()
  31. #define PB push_back
  32. #define MP make_pair
  33.  
  34. typedef long long LL;
  35. typedef vector<int> VI;
  36. typedef pair<int, int> PII;
  37.  
  38. const double PI = acos(-1.0);
  39. const int INF = 1000 * 1000 * 1000 + 7;
  40. const LL LINF = INF * (LL) INF;
  41. const int MOD = 1000 * 1000 * 1000 + 7;
  42.  
  43. const double EPS = 1e-6;
  44. const int MAX = 55;
  45.  
  46. int X[MAX], Y[MAX], Z[MAX];
  47. int VX[MAX], VY[MAX], VZ[MAX];
  48. double G[MAX][MAX];
  49. int U[MAX];
  50. double D[MAX];
  51. int F[MAX];
  52. int n;
  53.  
  54. vector<PII> prim(double time)
  55. {
  56. FOR(i, 0, n)
  57. FOR(j, 0, n)
  58. {
  59. double x = X[i] + time * VX[i];
  60. double y = Y[i] + time * VY[i];
  61. double z = Z[i] + time * VZ[i];
  62.  
  63. double xx = X[j] + time * VX[j];
  64. double yy = Y[j] + time * VY[j];
  65. double zz = Z[j] + time * VZ[j];
  66.  
  67. double dx = x - xx;
  68. double dy = y - yy;
  69. double dz = z - zz;
  70.  
  71. G[i][j] = dx * dx + dy * dy + dz * dz;
  72. }
  73.  
  74. FOR(i, 0, n)
  75. U[i] = 0, F[i] = -1, D[i] = 1e100;
  76. D[0] = 0;
  77. vector<PII> ANS;
  78.  
  79. FOR(it, 0, n)
  80. {
  81. int v = -1;
  82. FOR(i, 0, n)
  83. {
  84. if (U[i])continue;
  85. if (v == -1 || D[i] < D[v])
  86. v = i;
  87. }
  88. U[v] = 1;
  89. if (F[v] != -1)ANS.PB(MP(min(v, F[v]), max(v, F[v])));
  90. FOR(i, 0, n)
  91. {
  92. if (G[v][i] < D[i])
  93. {
  94. D[i] = G[v][i];
  95. F[i] = v;
  96. }
  97. }
  98. }
  99. sort(ALL(ANS));
  100. return ANS;
  101. }
  102.  
  103. int main()
  104. {
  105. int test = 0;
  106. while(cin >> n)
  107. {
  108. FOR(i, 0, n)
  109. {
  110. scanf("%d%d%d", X + i, Y + i, Z + i);
  111. scanf("%d%d%d", VX + i, VY + i, VZ + i);
  112. }
  113. double cur = 0;
  114. int ans = 1;
  115. while(true)
  116. {
  117. //cout << cur << endl;
  118. vector<PII> mst = prim(cur);
  119. double l = cur;
  120. double r = 1e5;
  121. FOR(it, 0, 50)
  122. {
  123. double m = (l + r) * .5;
  124. vector<PII> mm = prim(m);
  125. if (mm == mst)l = m;
  126. else r = m;
  127. }
  128. if (l > 1e4)break;
  129. ans++;
  130. cur = r;
  131. }
  132. printf("Case %d: %d\n",++test, ans);
  133.  
  134. }
  135.  
  136. return 0;
  137. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement