cockchaf.cpp
#include <stdio.h>
#include <math.h>
#include <vector>
#include <algorithm>
using namespace std;
#define HRange 100000
#define Nekonecno 1E20
struct Point {
int X,Y,Z;
};
struct TimeP {
double Time;
double OLen;
int EndP;
int MinSm;
};
int Seg[4000][2];
double SegTime[4000];
double SegLen[4000];
struct Point Latice[4000];
double EndT[2000][2];
int Hash[HRange];
int NextH[4000];
int LP;
int LaticeSeg[4000][4000];
int LaticeSegN[4000];
vector<TimeP> Fronta;
int HFce(int X,int Y,int Z) {
return (X*31+Y*12384+(Z^318276))%HRange;
};
double ScalMul(int X1,int X2) {
return (Latice[Seg[X1][1]].X-Latice[Seg[X1][0]].X)*(Latice[Seg[X2][1]].X-Latice[Seg[X2][0]].X) + (Latice[Seg[X1][1]].Y-Latice[Seg[X1][0]].Y)*(Latice[Seg[X2][1]].Y-Latice[Seg[X2][0]].Y) + (Latice[Seg[X1][1]].Z-Latice[Seg[X1][0]].Z)*(Latice[Seg[X2][1]].Z-Latice[Seg[X2][0]].Z);
};
bool FCompare(struct TimeP P1,struct TimeP P2) {
return (P1.Time > P2.Time);
};
double sqr(double x) {
return x*x;
};
int FindPoint(int X,int Y,int Z) {
int H;
int Pos,Last;
H = HFce(X,Y,Z);
Pos = Hash[H];
Last = -1;
while (Pos != -1) {
if ((X == Latice[Pos].X) && (Y == Latice[Pos].Y) && (Z == Latice[Pos].Z)) return Pos;
Last = Pos;
Pos = NextH[Pos];
};
Latice[LP].X = X;
Latice[LP].Y = Y;
Latice[LP].Z = Z;
if (Last == -1) {
Hash[H] = LP;
} else {
NextH[Last] = LP;
};
NextH[LP++]=-1;
return (LP-1);
};
int main() {
int i,j;
int N,S,T;
int Xf,Yf,Zf,Xt,Yt,Zt;
int X1,Y1,Z1,X2,Y2,Z2;
int St,En,P1,P2,SegN;
double Len,Len2;
struct TimeP Stav;
double Cas,OCas;
double DegRad;
int Stary,Novy,MinSmer;
double Min;
DegRad = 90/acos(0.0);
while (scanf("%d%d%d",&N,&S,&T) == 3) {
for (i=0;i<HRange;i++) {
Hash[i]=-1;
};
LP = 0;
SegN = 0;
scanf("%d%d%d%d%d%d",&Xf,&Yf,&Zf,&Xt,&Yt,&Zt);
St = FindPoint(Xf,Yf,Zf);
En = FindPoint(Xt,Yt,Zt);
//printf("%d %d\n",St,En);
for (i=0;i<N;i++) {
scanf("%d%d%d%d%d%d",&X1,&Y1,&Z1,&X2,&Y2,&Z2);
P1 = FindPoint(X1,Y1,Z1);
P2 = FindPoint(X2,Y2,Z2);
//printf("%d, %d %d\n",i,P1,P2);
Len = sqrt(sqr(X1-X2)+sqr(Y1-Y2)+sqr(Z1-Z2));
SegLen[SegN]=Len;
SegTime[SegN]=Nekonecno;
Seg[SegN][0]=P1;
Seg[SegN++][1]=P2;
SegLen[SegN]=Len;
SegTime[SegN]=Nekonecno;
Seg[SegN][0]=P2;
Seg[SegN++][1]=P1;
//printf("%d %d -> %d\n",SegN-1,P1,P2);
//printf("%d %d -> %d\n",SegN,P2,P1);
};
for (i=0;i<LP;i++) LaticeSegN[i]=0;
for (i=0;i<SegN;i++) {
P1 = Seg[i][0];
LaticeSeg[P1][LaticeSegN[P1]++]=i;
};
/*for (i=0;i<LP;i++) {
printf("%d - ",LaticeSegN[i]);
for (j=0;j<LaticeSegN[i];j++) printf("%d ",LaticeSeg[i][j]);
printf("\n");
}*/
if (St == En) {
printf("0.000\n");
} else {
Fronta.clear();
make_heap(Fronta.begin(),Fronta.end(),FCompare);
for (i=0;i<LaticeSegN[St];i++) {
Stav.Time = SegLen[LaticeSeg[St][i]]/S;
Stav.EndP = Seg[LaticeSeg[St][i]][1];
Stav.OLen = SegLen[LaticeSeg[St][i]];
Stav.MinSm = LaticeSeg[St][i];
SegTime[LaticeSeg[St][i]] = Stav.Time;
Fronta.push_back(Stav);
push_heap(Fronta.begin(),Fronta.end(),FCompare);
};
while (Fronta.size() > 0) {
pop_heap(Fronta.begin(),Fronta.end(),FCompare);
Stav = Fronta.back();
Fronta.pop_back();
Stary = Stav.EndP;
OCas = Stav.Time;
Len2 = Stav.OLen;
MinSmer = Stav.MinSm;
//printf("X %d %4.4f %d\n",Stary,OCas,Fronta.size());
for (i=0;i<LaticeSegN[Stary];i++) {
Novy = LaticeSeg[Stary][i];
Cas = ScalMul(MinSmer,Novy)/Len2/SegLen[Novy];
//printf("%4.4f ",Cas);
if (Cas > 1.0) Cas = 1.0;
if (Cas < -1.0) Cas = -1.0;
Cas = DegRad*acos(Cas);
//printf("%d %d %d %d %4.4f %4.4f\n",Stary,Novy,Seg[Novy][1],Novy,Cas,SegLen[Novy]);
Cas = Cas/T+SegLen[Novy]/S + OCas;
if (Cas < SegTime[Novy]) {
//printf("Novy %d %4.4f\n",Novy,Cas);
SegTime[Novy]=Cas;
Stav.Time = Cas;
Stav.EndP = Seg[Novy][1];
Stav.OLen = SegLen[Novy];
Stav.MinSm = Novy;
Fronta.push_back(Stav);
push_heap(Fronta.begin(),Fronta.end(),FCompare);
};
};
};
/*for (i=0;i<SegN;i++) {
printf("%4.4f\n",SegTime[i]);
};*/
Min = Nekonecno;
for (i=0;i<SegN;i++) if (Seg[i][1] == En) {
if (SegTime[i] < Min) Min = SegTime[i];
};
printf("%4.4f\n",Min);
};
};
return 0;
};