题意：
三维空间内有n（n<=50）个点，每个点有初始坐标和xyz和xyz三个方向上的速度dxdydz
求最小生成树变化的次数
分析：
最多啊n^2条边，最小生成树变化，无非是原来生成树中的某条边被新边替换
所以对每两条边计算可能出现这两条边相等的时间，称之为一个Event，（n^4个）
此时生成树可能会发生变化，对每个Event检查最小生成树有没有发生变化
总复杂度n^6，会炸
优化：对每个Event看这个时间点的两条相等的边（一条上升趋势A一条下降趋势B）
如果A在当前的生成树里面，则重新搞出生成树复杂度n^2，
这样可以减少切换次数，可以卡过去（lrj的分析= =）
流程：
首先读进去点，每个点6个参数，构造边Edges，//makeEdges
然后构造Events事件时间点，sort//makeEvents
构造初始状态的最小生成树//work
对每个时间点如果当前生成树上有边是此时的oldEdge，//work
则更新生成树//EndWork
代码有点长，有点烦，结构体多不要嫌烦，
#include<cstdio>
#include<cmath>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 9999;
const double EPS = 1e-6;
int n;
struct point{
double x,y,z,dx,dy,dz;
inline void read(){
scanf("%lf%lf%lf%lf%lf%lf",&x,&y,&z,&dx,&dy,&dz);
}
}po[N];
struct Edge{
double a,b,c;
int from,to;
bool operator < (const Edge &a)const{
return c < a.c;
}
}edges[N];
int E;
inline double sqr(double x){return x*x;}
inline void makeEdges(){
E = 0;
for (int i=1; i<n; i++){
for (int j=i+1;j<=n;j++){
edges[++E].a = sqr(po[i].dx - po[j].dx)
+ sqr(po[i].dy - po[j].dy)
+ sqr(po[i].dz - po[j].dz);
edges[E].b = 2*( (po[i].dx - po[j].dx)*(po[i].x - po[j].x)
+(po[i].dy - po[j].dy)*(po[i].y - po[j].y)
+(po[i].dz - po[j].dz)*(po[i].z - po[j].z));
edges[E].c = sqr(po[i].x - po[j].x)
+ sqr(po[i].y - po[j].y)
+ sqr(po[i].z - po[j].z);
edges[E].from = i;
edges[E].to = j;
}
}
sort(edges + 1,edges + E + 1);
}
struct Event{
double t;//time
int newE, oldE;
Event(double t=0,int n=0,int o=0):t(t),newE(n),oldE(o){}
bool operator < (const Event &a) const {
return t < a.t;
}
};
vector <Event> events;
inline void makeEvents(){
events.clear();
for (int i=1; i<E; i++){
for (int j=i+1;j<=E;j++){
int s1 = i, s2 = j;
if (edges[s1].a < edges[s2].a) swap(s1,s2);//*****
double a = edges[s1].a - edges[s2].a;
double b = edges[s1].b - edges[s2].b;
double c = edges[s1].c - edges[s2].c;
if (fabs(a) < EPS){//b*t + c = 0
if (fabs(b) < EPS) continue;
if (b>0){swap(s1,s2);b=-b;c=-c;}
if (c>0) events.push_back(Event(-c/b,s1,s2));
}else {
double delta = b*b - 4*a*c;
if (delta<EPS) continue;//no solution
delta = sqrt(delta);
double t1 = (-b-delta)/(2*a);
double t2 = (-b+delta)/(2*a);
if (t1>0)events.push_back(Event(t1,s1,s2));
if (t2>0)events.push_back(Event(t2,s2,s1));
}
}
}
sort(events.begin(),events.end());
}
int f[N], pos[N], e[N];
int F(int x){return f[x]==x?x:f[x]=F(f[x]);}
inline int work(){
for (int i=0;i<=n;i++)f[i]=i;
memset(pos, 0, sizeof(pos));
int cnt = 0;
for (int i=1;i<=E;i++){//kruskal
int x = F(edges[i].from);
int y = F(edges[i].to );
if (x==y) continue;
//printf("edge:%d-%d
",edges[i].from,edges[i].to);
f[x] = y;
e[pos[i]=++cnt] = i;
if (cnt==n-1)break;
}
int ans = 1;
for (int i=0;i<events.size();i++){
if (!pos[events[i].oldE]) continue;
if ( pos[events[i].newE]) continue;
for (int i=0; i<=n; i++) f[i] = i ;
int oldPos = pos[events[i].oldE];
for (int j = 1;j<n;j++){
if (j==oldPos)continue;
int x = F(edges[e[j]].from);
int y = F(edges[e[j]].to );
if (x != y) f[x] = y;
}
int x = F(edges[events[i].newE].from);
int y = F(edges[events[i].newE].to );
if (x == y) continue;
ans ++;
pos[events[i].newE] = oldPos;
e[oldPos] = events[i].newE;
pos[events[i].oldE] = 0;
}
return ans;
}
int main(){
//freopen("in.txt","r",stdin);
for (int cas=0;~scanf("%d",&n);){
for (int i=1;i<=n;i++)po[i].read();
makeEdges();
makeEvents();
int ans = work();
printf("Case %d: %d
",++cas,ans);
}
return 0;
}
