Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <sstream>
- #include <iomanip>
- #include <cstdio>
- #include <cstdlib>
- #include <cmath>
- #include <cctype>
- #include <cstring>
- #include <vector>
- #include <list>
- #include <queue>
- #include <deque>
- #include <stack>
- #include <map>
- #include <set>
- #include <algorithm>
- #include <iterator>
- #include <bitset>
- #include <ctime>
- #include <complex>
- using namespace std;
- #define FOR(i,a,b) for (int i = (a); i < (b); i++)
- #define RFOR(i,b,a) for (int i = (b)-1; i >= (a); i--)
- #define ITER(it,a) for (__typeof(a.begin()) it = a.begin(); it != a.end(); it++)
- #define FILL(a,value) memset(a, value, sizeof(a))
- #define SZ(a) (int)a.size()
- #define ALL(a) a.begin(), a.end()
- #define PB push_back
- #define MP make_pair
- typedef long long LL;
- typedef vector<int> VI;
- typedef pair<int, int> PII;
- const double PI = acos(-1.0);
- const int INF = 1000 * 1000 * 1000 + 7;
- const LL LINF = INF * (LL) INF;
- const int MOD = 1000 * 1000 * 1000 + 7;
- const double EPS = 1e-6;
- const int MAX = 55;
- int X[MAX], Y[MAX], Z[MAX];
- int VX[MAX], VY[MAX], VZ[MAX];
- double G[MAX][MAX];
- int U[MAX];
- double D[MAX];
- int F[MAX];
- int n;
- vector<PII> prim(double time)
- {
- FOR(i, 0, n)
- FOR(j, 0, n)
- {
- double x = X[i] + time * VX[i];
- double y = Y[i] + time * VY[i];
- double z = Z[i] + time * VZ[i];
- double xx = X[j] + time * VX[j];
- double yy = Y[j] + time * VY[j];
- double zz = Z[j] + time * VZ[j];
- double dx = x - xx;
- double dy = y - yy;
- double dz = z - zz;
- G[i][j] = dx * dx + dy * dy + dz * dz;
- }
- FOR(i, 0, n)
- U[i] = 0, F[i] = -1, D[i] = 1e100;
- D[0] = 0;
- vector<PII> ANS;
- FOR(it, 0, n)
- {
- int v = -1;
- FOR(i, 0, n)
- {
- if (U[i])continue;
- if (v == -1 || D[i] < D[v])
- v = i;
- }
- U[v] = 1;
- if (F[v] != -1)ANS.PB(MP(min(v, F[v]), max(v, F[v])));
- FOR(i, 0, n)
- {
- if (G[v][i] < D[i])
- {
- D[i] = G[v][i];
- F[i] = v;
- }
- }
- }
- sort(ALL(ANS));
- return ANS;
- }
- int main()
- {
- int test = 0;
- while(cin >> n)
- {
- FOR(i, 0, n)
- {
- scanf("%d%d%d", X + i, Y + i, Z + i);
- scanf("%d%d%d", VX + i, VY + i, VZ + i);
- }
- double cur = 0;
- int ans = 1;
- while(true)
- {
- //cout << cur << endl;
- vector<PII> mst = prim(cur);
- double l = cur;
- double r = 1e5;
- FOR(it, 0, 50)
- {
- double m = (l + r) * .5;
- vector<PII> mm = prim(m);
- if (mm == mst)l = m;
- else r = m;
- }
- if (l > 1e4)break;
- ans++;
- cur = r;
- }
- printf("Case %d: %d\n",++test, ans);
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement