Source code for submission s1149

cockchaf.cpp

  1. #include <stdio.h>
  2. #include <math.h>
  3. #include <vector>
  4. #include <algorithm>
  5. using namespace std;
  6.  
  7. #define HRange 100000
  8. #define Nekonecno 1E20
  9.  
  10. struct Point {
  11. int X,Y,Z;
  12. };
  13.  
  14. struct TimeP {
  15. double Time;
  16. double OLen;
  17. int EndP;
  18. int MinSm;
  19. };
  20.  
  21. int Seg[4000][2];
  22. double SegTime[4000];
  23. double SegLen[4000];
  24. struct Point Latice[4000];
  25. double EndT[2000][2];
  26. int Hash[HRange];
  27. int NextH[4000];
  28. int LP;
  29. int LaticeSeg[4000][4000];
  30. int LaticeSegN[4000];
  31.  
  32. vector<TimeP> Fronta;
  33.  
  34. int HFce(int X,int Y,int Z) {
  35. return (X*31+Y*12384+(Z^318276))%HRange;
  36. };
  37.  
  38. double ScalMul(int X1,int X2) {
  39. 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);
  40. };
  41.  
  42. bool FCompare(struct TimeP P1,struct TimeP P2) {
  43. return (P1.Time > P2.Time);
  44. };
  45.  
  46. double sqr(double x) {
  47. return x*x;
  48. };
  49.  
  50. int FindPoint(int X,int Y,int Z) {
  51. int H;
  52. int Pos,Last;
  53.  
  54. H = HFce(X,Y,Z);
  55. Pos = Hash[H];
  56. Last = -1;
  57. while (Pos != -1) {
  58. if ((X == Latice[Pos].X) && (Y == Latice[Pos].Y) && (Z == Latice[Pos].Z)) return Pos;
  59. Last = Pos;
  60. Pos = NextH[Pos];
  61. };
  62. Latice[LP].X = X;
  63. Latice[LP].Y = Y;
  64. Latice[LP].Z = Z;
  65. if (Last == -1) {
  66. Hash[H] = LP;
  67. } else {
  68. NextH[Last] = LP;
  69. };
  70. NextH[LP++]=-1;
  71. return (LP-1);
  72. };
  73.  
  74. int main() {
  75. int i,j;
  76. int N,S,T;
  77. int Xf,Yf,Zf,Xt,Yt,Zt;
  78. int X1,Y1,Z1,X2,Y2,Z2;
  79. int St,En,P1,P2,SegN;
  80. double Len,Len2;
  81. struct TimeP Stav;
  82. double Cas,OCas;
  83. double DegRad;
  84. int Stary,Novy,MinSmer;
  85. double Min;
  86.  
  87. DegRad = 90/acos(0.0);
  88.  
  89. while (scanf("%d%d%d",&N,&S,&T) == 3) {
  90. for (i=0;i<HRange;i++) {
  91. Hash[i]=-1;
  92. };
  93. LP = 0;
  94. SegN = 0;
  95. scanf("%d%d%d%d%d%d",&Xf,&Yf,&Zf,&Xt,&Yt,&Zt);
  96. St = FindPoint(Xf,Yf,Zf);
  97. En = FindPoint(Xt,Yt,Zt);
  98. //printf("%d %d\n",St,En);
  99. for (i=0;i<N;i++) {
  100. scanf("%d%d%d%d%d%d",&X1,&Y1,&Z1,&X2,&Y2,&Z2);
  101. P1 = FindPoint(X1,Y1,Z1);
  102. P2 = FindPoint(X2,Y2,Z2);
  103. //printf("%d, %d %d\n",i,P1,P2);
  104. Len = sqrt(sqr(X1-X2)+sqr(Y1-Y2)+sqr(Z1-Z2));
  105. SegLen[SegN]=Len;
  106. SegTime[SegN]=Nekonecno;
  107. Seg[SegN][0]=P1;
  108. Seg[SegN++][1]=P2;
  109. SegLen[SegN]=Len;
  110. SegTime[SegN]=Nekonecno;
  111. Seg[SegN][0]=P2;
  112. Seg[SegN++][1]=P1;
  113. //printf("%d %d -> %d\n",SegN-1,P1,P2);
  114. //printf("%d %d -> %d\n",SegN,P2,P1);
  115. };
  116. for (i=0;i<LP;i++) LaticeSegN[i]=0;
  117. for (i=0;i<SegN;i++) {
  118. P1 = Seg[i][0];
  119. LaticeSeg[P1][LaticeSegN[P1]++]=i;
  120. };
  121. /*for (i=0;i<LP;i++) {
  122. printf("%d - ",LaticeSegN[i]);
  123. for (j=0;j<LaticeSegN[i];j++) printf("%d ",LaticeSeg[i][j]);
  124. printf("\n");
  125. }*/
  126. if (St == En) {
  127. printf("0.000\n");
  128. } else {
  129. Fronta.clear();
  130. make_heap(Fronta.begin(),Fronta.end(),FCompare);
  131. for (i=0;i<LaticeSegN[St];i++) {
  132. Stav.Time = SegLen[LaticeSeg[St][i]]/S;
  133. Stav.EndP = Seg[LaticeSeg[St][i]][1];
  134. Stav.OLen = SegLen[LaticeSeg[St][i]];
  135. Stav.MinSm = LaticeSeg[St][i];
  136. SegTime[LaticeSeg[St][i]] = Stav.Time;
  137. Fronta.push_back(Stav);
  138. push_heap(Fronta.begin(),Fronta.end(),FCompare);
  139. };
  140. while (Fronta.size() > 0) {
  141. pop_heap(Fronta.begin(),Fronta.end(),FCompare);
  142. Stav = Fronta.back();
  143. Fronta.pop_back();
  144. Stary = Stav.EndP;
  145. OCas = Stav.Time;
  146. Len2 = Stav.OLen;
  147. MinSmer = Stav.MinSm;
  148. //printf("X %d %4.4f %d\n",Stary,OCas,Fronta.size());
  149. for (i=0;i<LaticeSegN[Stary];i++) {
  150. Novy = LaticeSeg[Stary][i];
  151. Cas = ScalMul(MinSmer,Novy)/Len2/SegLen[Novy];
  152. //printf("%4.4f ",Cas);
  153. if (Cas > 1.0) Cas = 1.0;
  154. if (Cas < -1.0) Cas = -1.0;
  155. Cas = DegRad*acos(Cas);
  156. //printf("%d %d %d %d %4.4f %4.4f\n",Stary,Novy,Seg[Novy][1],Novy,Cas,SegLen[Novy]);
  157. Cas = Cas/T+SegLen[Novy]/S + OCas;
  158. if (Cas < SegTime[Novy]) {
  159. //printf("Novy %d %4.4f\n",Novy,Cas);
  160. SegTime[Novy]=Cas;
  161. Stav.Time = Cas;
  162. Stav.EndP = Seg[Novy][1];
  163. Stav.OLen = SegLen[Novy];
  164. Stav.MinSm = Novy;
  165. Fronta.push_back(Stav);
  166. push_heap(Fronta.begin(),Fronta.end(),FCompare);
  167. };
  168. };
  169. };
  170. /*for (i=0;i<SegN;i++) {
  171.   printf("%4.4f\n",SegTime[i]);
  172. };*/
  173. Min = Nekonecno;
  174. for (i=0;i<SegN;i++) if (Seg[i][1] == En) {
  175. if (SegTime[i] < Min) Min = SegTime[i];
  176. };
  177. printf("%4.4f\n",Min);
  178. };
  179. };
  180. return 0;
  181. };
  182.