Source code for submission s1393

cockchaf.cpp

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <math.h>
  4. #include <map>
  5. #include <set>
  6. #include <algorithm>
  7.  
  8. #define MAXM 4000
  9.  
  10. using namespace std;
  11.  
  12. typedef struct POINT
  13. {
  14. int x;
  15. int y;
  16. int z;
  17.  
  18. POINT() {}
  19. POINT(int x, int y, int z): x(x), y(y), z(z) {}
  20.  
  21. bool operator < (const POINT& p) const
  22. {
  23. if(x < p.x) return 1;
  24. if((x == p.x) && (y < p.y)) return 1;
  25. if((x == p.x) && (y == p.y) && (z < p.z)) return 1;
  26. return 0;
  27. }
  28. }
  29. POINT;
  30.  
  31. typedef struct EDGE
  32. {
  33. POINT p1;
  34. POINT p2;
  35. }
  36. EDGE;
  37.  
  38. typedef struct NEWEDGE
  39. {
  40. int v1;
  41. int v2;
  42. }
  43. NEWEDGE;
  44.  
  45. typedef struct SETITEM
  46. {
  47. double d;
  48. int v;
  49.  
  50. SETITEM() {}
  51. SETITEM(double d, int v): d(d), v(v) {}
  52.  
  53. bool operator < (const SETITEM& i) const
  54. {
  55. if(d < i.d) return 1;
  56. if((d == i.d) && (v < i.v)) return 1;
  57. return 0;
  58. }
  59. }
  60. SETITEM;
  61.  
  62. typedef struct FOL
  63. {
  64. int v;
  65. int i;
  66. }
  67. FOL;
  68.  
  69. EDGE Edge[MAXM];
  70. NEWEDGE NewEdge[MAXM];
  71.  
  72. int Degree[MAXM];
  73. int CurIndex[MAXM];
  74. FOL Fol[MAXM * 2];
  75. int iFol[MAXM];
  76. POINT Point[MAXM];
  77.  
  78. double Dist[MAXM * 2];
  79.  
  80. double GetLength(double x1, double y1, double z1)
  81. {
  82. return sqrt((x1 * x1) + (y1 * y1) + (z1 * z1));
  83. }
  84.  
  85. double GetLength(POINT& p1, POINT& p2)
  86. {
  87. return GetLength(p1.x - p2.x, p1.y - p2.y, p1.z - p2.z);
  88. }
  89.  
  90. double GetAngle(double x1, double y1, double z1, double x2, double y2, double z2)
  91. {
  92. return acos(
  93. ((x1 * x2) + (y1 * y2) + (z1 * z2))
  94. /
  95. (GetLength(x1, y1, z1) * GetLength(x2, y2, z2))
  96. ) * 180 / (atan(1) * 4);
  97. }
  98.  
  99. /*void Enqueue(set<SETITEM>& Set, int w)
  100. {
  101. set<SETITEM>::iterator it = Set.find(w);
  102.  
  103. if((it != Set.end()) && (Dist[w] < it->d))
  104. {
  105. Set.erase(it);
  106. }
  107.  
  108. Set.insert(SETITEM(Dist[w], w));
  109. }*/
  110.  
  111. int GetIndex(int w)
  112. {
  113. if(w % 2)
  114. {
  115. return NewEdge[w / 2].v2;
  116. }
  117. else
  118. {
  119. return NewEdge[w / 2].v1;
  120. }
  121. }
  122.  
  123. int main()
  124. {
  125. int m, sss, ttt;
  126. int x1, y1, z1, x2, y2, z2;
  127. while(scanf("%d%d%d", &m, &sss, &ttt) > 0)
  128. {
  129. map<POINT, int> Map;
  130. set<SETITEM> Set;
  131.  
  132. scanf("%d%d%d%d%d%d", &x1, &y1, &z1, &x2, &y2, &z2);
  133. if((x1 == x2) && (y1 == y2) && (z1 == z2))
  134. {
  135. printf("0.0\n");
  136. continue;
  137. }
  138.  
  139. int n = 0;
  140. for(int i = 0; i < m; i++)
  141. {
  142. scanf("%d%d%d%d%d%d",
  143. &(Edge[i].p1.x),
  144. &(Edge[i].p1.y),
  145. &(Edge[i].p1.z),
  146. &(Edge[i].p2.x),
  147. &(Edge[i].p2.y),
  148. &(Edge[i].p2.z));
  149.  
  150. if(Map.find(Edge[i].p1) == Map.end())
  151. {
  152. Map[Edge[i].p1] = n;
  153. Point[n++] = Edge[i].p1;
  154.  
  155. //printf("1 %d\n", Map[Edge[i].p1]);
  156. }
  157.  
  158. if(Map.find(Edge[i].p2) == Map.end())
  159. {
  160. Map[Edge[i].p2] = n;
  161. Point[n++] = Edge[i].p2;
  162.  
  163. //printf("2 %d\n", Map[Edge[i].p2]);
  164. }
  165. }
  166.  
  167. for(int i = 0; i < m; i++)
  168. {
  169. NewEdge[i].v1 = Map[Edge[i].p1];
  170. NewEdge[i].v2 = Map[Edge[i].p2];
  171.  
  172. //printf("%d->%d\n", NewEdge[0].v1, NewEdge[0].v2);
  173.  
  174. Degree[NewEdge[i].v1]++;
  175. Degree[NewEdge[i].v2]++;
  176. }
  177.  
  178. iFol[0] = 0;
  179. for(int i = 0; i < n; i++)
  180. {
  181. iFol[i + 1] = iFol[i] + Degree[i];
  182. }
  183.  
  184. for(int i = 0; i < n; i++)
  185. {
  186. CurIndex[i] = 0;
  187. }
  188.  
  189. int e;
  190. for(int i = 0; i < m; i++)
  191. {
  192. e = NewEdge[i].v1;
  193. Fol[iFol[e] + CurIndex[e]++] = (FOL) {NewEdge[i].v2, (i * 2) + 1};
  194. e = NewEdge[i].v2;
  195. Fol[iFol[e] + CurIndex[e]++] = (FOL) {NewEdge[i].v1, i * 2};
  196. }
  197.  
  198. for(int i = 0; i < m * 2; i++)
  199. {
  200. Dist[i] = 1e18;
  201. }
  202.  
  203. int wStart = Map[POINT(x1, y1, z1)];
  204. int wGoal = Map[POINT(x2, y2, z2)];
  205.  
  206. //printf("%d->%d\n", NewEdge[0].v1, NewEdge[0].v2);
  207.  
  208. for(int i = 0; i < m; i++)
  209. {
  210. if(NewEdge[i].v1 == wStart)
  211. {
  212. Dist[(i * 2) + 1] = GetLength(Edge[i].p1, Edge[i].p2);
  213. int w = (i * 2) + 1;
  214. Set.insert(SETITEM(Dist[w], w));
  215. }
  216.  
  217. if(NewEdge[i].v2 == wStart)
  218. {
  219. Dist[(i * 2) + 0] = GetLength(Edge[i].p1, Edge[i].p2);
  220. int w = (i * 2) + 0;
  221. Set.insert(SETITEM(Dist[w], w));
  222. }
  223. }
  224.  
  225. while(!(Set.empty()))
  226. {
  227. SETITEM Item = *(Set.begin());
  228. Set.erase(Set.begin());
  229. int v = GetIndex(Item.v);
  230.  
  231. //printf("%d\n", Item.v);
  232.  
  233. if(v == wGoal)
  234. {
  235. printf("%lf\n", Dist[Item.v]);
  236. break;
  237. }
  238.  
  239. for(int i = iFol[v]; i < iFol[v + 1]; i++)
  240. {
  241. FOL t = Fol[i];
  242.  
  243. int r1, r2, r3 = t.i;
  244. if(Item.v % 2)
  245. {
  246. r1 = GetIndex(Item.v / 2);
  247. r2 = GetIndex((Item.v / 2) + 1);
  248. }
  249. else
  250. {
  251. r2 = GetIndex(Item.v / 2);
  252. r1 = GetIndex((Item.v / 2) + 1);
  253. }
  254.  
  255. double x1 = Point[r1].x - Point[r2].x;
  256. double y1 = Point[r1].y - Point[r2].y;
  257. double z1 = Point[r1].z - Point[r2].z;
  258.  
  259. double x2 = Point[r2].x - Point[r3].x;
  260. double y2 = Point[r2].y - Point[r3].y;
  261. double z2 = Point[r2].z - Point[r3].z;
  262.  
  263. double prev = Dist[Item.v];
  264. double angle = GetAngle(x1, y1, z1, x2, y2, z2) / ttt;
  265. double length = GetLength(Point[v], Point[GetIndex(t.i)]) / sss;
  266.  
  267. double newDist = prev + angle + length;
  268.  
  269. if(Dist[t.i] == 1e18)
  270. {
  271. Dist[t.i] = newDist;
  272. Set.insert(SETITEM(Dist[t.i], t.i));
  273. }
  274. else if(newDist < Dist[t.i])
  275. {
  276. Set.erase(SETITEM(Dist[t.i], t.i));
  277. Dist[t.i] = newDist;
  278. Set.insert(SETITEM(Dist[t.i], t.i));
  279. }
  280. }
  281. }
  282. }
  283.  
  284. //printf("%lf\n", GetAngle(1, 0, 0, -3, 0, 0));
  285.  
  286. return 0;
  287. }
  288.