Advertisement
Guest User

Untitled

a guest
Jul 20th, 2018
73
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 7.67 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define dbg(x) //cerr<<#x": "<<x<<"\n"
  4. #define dbg_p(x) cerr<<#x": "<<x.first<<","<<x.second<<"\n"
  5. #define dbg_v(x, n) //do{cerr<<#x"[]: ";for(int _=0;_<n;++_)cerr<<x[_]<<" ";cerr<<'\n';}while(0)
  6. #define dbg_ok //cerr<<"OK!\n"
  7.  
  8. #define DMAX
  9. #define NMAX
  10. #define MMAX
  11.  
  12. #define st first
  13. #define nd second
  14.  
  15. #define EPS 1e-9
  16. const double PI = acos(-1);
  17.  
  18. using namespace std;
  19.  
  20. int n, k;
  21. string s;
  22.  
  23.  
  24.  
  25. template<class T1,class T2>
  26. ostream& operator<<(ostream& out, pair<T1, T2> p) {
  27. return out << "(" << p.st << ", " << p.nd << ")";
  28. }
  29. template<class T>
  30. ostream& operator<<(ostream& out, vector<T> v) {
  31. out << v.size() << '\n';
  32. for(auto e : v) out << e << ' ';
  33. return out;
  34. }
  35.  
  36.  
  37. struct point{
  38. double x, y;
  39.  
  40. point() { }
  41. point(const point &a) {x = a.x, y = a.y;}
  42. point(double _x, double _y) { x = _x; y = _y; }
  43.  
  44. point operator-(point a) {return point(x - a.x, y - a.y);}
  45. point operator+(point a) {return point(x + a.x, y + a.y);}
  46. point operator*(double val) {return point(x * val, y * val);}
  47. point operator/(double val) {return point(x / val, y / val);}
  48.  
  49. bool operator<(const point &a) const { if(fabs(x - a.x) < EPS) {if(fabs(y - a.y) < EPS) return false; return y < a.y;} return x < a.x; }
  50. bool operator==(const point &a) const { if(fabs(x - a.x) < EPS) if(fabs(y - a.y) < EPS) return true; return false; }
  51.  
  52. point rot() {return point(-y, x);}
  53. double norm() {return x*x + y*y; }
  54. double len() {return sqrt(norm()); }
  55.  
  56. void rot(long double alfa) {
  57. long double cx = x;
  58. x = x * cos(alfa) - y * sin(alfa);
  59. y = y * cos(alfa) + cx * sin(alfa);
  60. }
  61. };
  62.  
  63. ostream& operator<<(ostream& out, point p) { return out << p.x << ' ' << p.y; }
  64.  
  65. struct line
  66. {
  67. double m, n;
  68.  
  69. line(point A, point B) {
  70. m = (A.y - B.y) / (A.x - B.x) ;
  71. n = A.y - m * A.x;
  72. }
  73.  
  74. line(point A, double _m) {
  75. // linia de panta _m care trece prin punctul A
  76. m = _m;
  77. n = A.y - m * A.x;
  78. }
  79.  
  80. line(double _m, double _n) {
  81. m = _m;
  82. n = _n;
  83. }
  84.  
  85. point intersect(line l) {
  86. // returneaza punctul in care se intersecteaza linia this cu linia l
  87. point O;
  88. //if(m == l.m)
  89. // return
  90. O.x = (l.n - n) / (m - l.m);
  91. O.y = m * O.x + n;
  92. return O;
  93. }
  94.  
  95. };
  96.  
  97.  
  98. long double dist(point a, point b)
  99. {
  100. long double X = a.x - b.x;
  101. long double Y = a.y - b.y;
  102. return sqrt(X * X + Y * Y);
  103. }
  104.  
  105. struct circle {
  106. point o;
  107. double r;
  108.  
  109. circle() {}
  110. circle(point a, point b, point c) {
  111. point mab = (a + b) / 2.;
  112. point mbc = (c + b) / 2.;
  113. line ab(a, b), bc(b, c);
  114. line ab1(mab, -1.0/ab.m);
  115. line bc1(mbc, -1.0/bc.m);
  116. o = ab1.intersect(bc1);
  117. r = dist(o, a);
  118. }
  119.  
  120. bool operator==(circle & c) {
  121. if(fabs(c.r - r) > EPS) return false;
  122. if(fabs(c.o.x - o.x) > EPS) return false;
  123. if(fabs(c.o.y - o.y) > EPS) return false;
  124. return true;
  125. }
  126.  
  127. vector <point> intersect(circle c) {
  128. long double p, h, a, area, d;
  129. d = dist(o, c.o);
  130. if(d > r + c.r) return {};
  131. if(d < fabs(r - c.r)) return {};
  132. a = 0.5 * (d + (r * r - c.r * c.r) / d );
  133. h = sqrt(r * r - a * a);
  134. point B = o + (c.o - o) * a / d;
  135. point aa = c.o - o;
  136. point ff(-aa.y, aa.x);//aa.y = -aa.y;
  137. aa = ff * h / d;
  138. return {B + aa, B - aa};
  139. }
  140.  
  141. };
  142.  
  143. struct seg {
  144. point a, b;
  145.  
  146. seg(point _a, point _b) { a = _a, b = _b; };
  147. };
  148.  
  149.  
  150. istream& operator>>(istream& in, point &p) { return in >> p.x >> p.y; }
  151.  
  152. istream& operator>>(istream& in, circle &c) { return in >> c.o >> c.r; }
  153.  
  154. istream& operator>>(istream& in, seg &s) { return in >> s.a >> s.b; }
  155.  
  156. long double area(point a, point b, point c) {
  157. return a.x * b.y + b.x * c.y + c.x * a.y - a.y * b.x - b.y * c.x - c.y * a.x;
  158. }
  159.  
  160. bool isObtouseAngle(point A, point B, point C) {
  161. //check if A angle is obtuse
  162. double a = dist(B, C);
  163. double b = dist(A, C);
  164. double c = dist(B, A);
  165. a *= a;
  166. b *= b;
  167. c *= c;
  168. if(b + c < a)
  169. return true;
  170. return false;
  171. }
  172.  
  173. double dist(point p, seg s) {
  174. if(isObtouseAngle(s.a, s.b, p) || dist(s.a, s.b) <= EPS || isObtouseAngle(s.b, s.a, p))
  175. return min(dist(p, s.a), dist(p, s.b));
  176. return fabs(area(p, s.a, s.b)) / dist(s.a, s.b);
  177. }
  178.  
  179.  
  180. bool checkInt(seg a, seg b)
  181. {
  182. // if( area(a[p], b[p], a[q]) * area(a[p], b[p], b[q]) > 0 )
  183. // return false;
  184. // if( area(a[q], b[q], a[p]) * area(a[q], b[q], b[p]) > 0 )
  185. // return false;
  186. // if( area(a[q], b[q], a[p]) * area(a[q], b[q], b[p]) == 0 && area(a[p], b[p], a[q]) * area(a[p], b[p], b[q]) == 0)
  187. // if( max(a[q].x, b[q].x) < min(a[p].x, b[p].x) || min(a[q].x, b[q].x) > max(a[p].x, b[p].x))
  188. // return false;
  189. // return true;
  190.  
  191. if( area(a.a, a.b, b.a) * area(a.a, a.b, b.b) > 0 )
  192. return false;
  193. if( area(b.a, b.b, a.a) * area(b.a, b.b, a.b) > 0 )
  194. return false;
  195. if(dist(a.a, b.a) <= EPS)
  196. return false;
  197. if(dist(a.a, b.b) <= EPS)
  198. return false;
  199. if(dist(a.b, b.a) <= EPS)
  200. return false;
  201. if(dist(a.b, b.b) <= EPS)
  202. return false;
  203. if( fabs(area(b.a, b.b, a.a) * area(b.a, b.b, a.b)) < EPS && fabs(area(a.a, a.b, b.a) * area(a.a, a.b, b.b)) < EPS)
  204. if( max(b.a.x, b.b.x) < min(a.a.x, a.b.x) || min(b.a.x, b.b.x) > max(a.a.x, a.b.x))
  205. return false;
  206. return true;
  207. }
  208.  
  209. point cmp_point;
  210. bool cmp(point a, point b) {
  211. return area(cmp_point, a, b) >= 0;
  212. }
  213.  
  214. vector <point> hull(vector <point> &pts) {
  215.  
  216. int ind = 0;
  217. for(int i = 1; i < pts.size(); i++)
  218. if(pts[i] < pts[ind])
  219. ind = i;
  220. swap(pts[pts.size() - 1], pts[ind]);
  221. cmp_point = pts.back();
  222. pts.pop_back();
  223.  
  224. sort(pts.begin(), pts.end(), cmp);
  225.  
  226. vector <point> hull;
  227. hull.push_back(cmp_point);
  228. for(int i = 0; i < pts.size(); i++) {
  229. while (hull.size() > 2 && area(hull[hull.size()-2],hull[hull.size() - 1],pts[i]) < 0) {
  230. hull.pop_back();
  231. }
  232. hull.push_back(pts[i]);
  233. }
  234. return hull;
  235. }
  236.  
  237. vector <int> pol[130];
  238. point src, dest, p[330];
  239. int pnr[330], sz = 0;
  240. vector <pair<int, double> > v[330];
  241.  
  242. bool collision(seg a, int black) {
  243. for(int i = 1; i <= n; i++) {
  244. if(i == black)
  245. continue;
  246. for(int j = 0; j < pol[i].size(); j++) {
  247. int i1 = pol[i][j];
  248. int i2 = pol[i][(j + 1) % pol[i].size()];
  249. if(checkInt(a, seg(p[i1], p[i2]))) {
  250. dbg(i1);
  251. dbg(i2);
  252. return true;
  253. }
  254. }
  255. }
  256. return false;
  257. }
  258.  
  259. double dijkstra(int src) {
  260. double d[330];
  261. for(int i = 0; i <= 322; i++)
  262. d[i] = 2e9;
  263.  
  264. priority_queue <pair<double, int> > pq;
  265. pq.push({0, src});
  266. d[src] = 0;
  267.  
  268. while(!pq.empty()) {
  269. auto cur = pq.top();
  270. pq.pop();
  271.  
  272. for(auto i : v[cur.nd])
  273. if(d[i.st] > d[cur.nd] + i.nd) {
  274. d[i.st] = d[cur.nd] + i.nd;
  275. pq.push({-d[i.st], i.st});
  276. }
  277. }
  278. dbg_v(d, sz + 1);
  279. if(d[sz] < 2e9 - 10)
  280. return d[sz];
  281. else
  282. return -1;
  283. }
  284.  
  285.  
  286. void solve() {
  287. cin >> n;
  288.  
  289. cin >> src >> dest;
  290. for(int i = 1; i <= n; i++) {
  291. cin >> k;
  292. for(int j = 0; j < k; j++) {
  293. cin >> p[++sz];
  294. pol[i].push_back(sz);
  295. }
  296. }
  297. p[0] = src;
  298. pnr[0] = -1;
  299. sz++;
  300. pnr[sz] = -2;
  301. p[sz] = dest;
  302. for(int i = 0; i <= sz; i++)
  303. for(int j = i + 1; j <= sz; j++) {
  304. if(pnr[i] != pnr[j] && !collision(seg(p[i], p[j]), -1)) {
  305. double d = dist(p[i], p[j]);
  306. v[i].push_back({j, d});
  307. v[j].push_back({i, d});
  308. }
  309. }
  310.  
  311. for(int i = 1; i <= n; i++) {
  312. for(int j = 0; j < pol[i].size(); j++) {
  313. int i1 = pol[i][j];
  314. int i2 = pol[i][(j + 1) % pol[i].size()];
  315. if(!collision(seg(p[i1], p[i2]), i)) {
  316. double d = dist(p[i1], p[i2]);
  317. v[i1].push_back({i2, d});
  318. v[i2].push_back({i1, d});
  319. }
  320. }
  321. }
  322. dbg_ok;
  323. dbg(collision(seg(p[0], p[sz]), -1));
  324. cout << dijkstra(0) << '\n';
  325. for(int i = 0; i <= sz; i++)
  326. v[i].clear();
  327. }
  328.  
  329.  
  330.  
  331. int main()
  332. {
  333. ios_base::sync_with_stdio(false);
  334. cout << fixed << setprecision(9);
  335. int t;
  336. cin >> t;
  337. while(t--)
  338. solve();
  339. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement