Advertisement
Guest User

Untitled

a guest
Mar 20th, 2019
105
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 8.06 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #pragma comment(linker, "/stack:200000000")
  3. #pragma GCC optimize("Ofast")
  4. #pragma GCC optimize("unroll-loops")
  5. #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  6.  
  7. #include <set>
  8. #include <map>
  9. #include <deque>
  10. #include <cmath>
  11. #include <queue>
  12. #include <random>
  13. #include <bitset>
  14. #include <time.h>
  15. #include <string>
  16. #include <chrono>
  17. #include <cstdio>
  18. #include <vector>
  19. #include <cstdlib>
  20. #include <iomanip>
  21. #include <cassert>
  22. #include <iostream>
  23. #include <algorithm>
  24. #include <unordered_map>
  25. #include <unordered_set>
  26. //++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++
  27. #define itn int
  28. #define endl '\n'
  29. #define mp make_pair
  30. #define pbc push_back
  31. #define pob pop_back()
  32. #define empb emplace_back
  33. #define sp system("pause")
  34. #define queuel queue<long long>
  35. #define matrix vector<vector<ll>>
  36. #define all(x) (x).begin(),(x).end()
  37. #define rall(x) (x).rbegin(),(x).rend()
  38. #define pin(p) cin >> p.first >> p.second;
  39. #define rev(v) reverse(v.begin(),v.end());
  40. #define mx(v) max_element(v.begin(), v.end());
  41. #define mn(v) min_element(v.begin(), v.end());
  42. #define dig(c) (c >=' 0' && c <= '9') ? 1 : 0
  43. #define sout(s, c) for(auto i : s) cout << i << c;
  44. #define pout(p) cout << p.first << " " << p.second;
  45. #define er(v, l, r) erase(v.begin() + l, v.begin() + r);
  46. #define vin(v) for(ll i = 0; i < v.size(); i++) cin >> v[i];
  47. #define vout(v, c) for(int i = 0; i < v.size(); i++) cout << v[i] << c;
  48. #define pushi(v, a) for(int i = 0; i < a.size(); i++) v.push_back(a[i]);
  49. #define sin(s, n) for(int i = 0; i < n; i++){int a; cin >> a; s.insert(a);}
  50. #define fastio() ios_base::sync_with_stdio(0); cout.tie(0); cin.tie(0);
  51. //++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++
  52. using namespace std;
  53. /*▄███████▀▀▀▀▀▀███████▄
  54. ░▐████▀▒ЗАПУСКАЕМ▒▀██████▄
  55. ░███▀▒▒▒▒▒ДЯДЮ▒▒▒▒▒▒▀█████
  56. ░▐██▒▒▒▒▒▒БОГДАНА▒▒▒▒▒████▌
  57. ░▐█▌▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒████▌
  58. ░░█▒▄▀▀▀▀▀▄▒▒▄▀▀▀▀▀▄▒▐███▌
  59. ░░░▐░░░▄▄░░▌▐░░░▄▄░░▌▐███▌
  60. ░▄▀▌░░░▀▀░░▌▐░░░▀▀░░▌▒▀▒█▌
  61. ░▌▒▀▄░░░░▄▀▒▒▀▄░░░▄▀▒▒▄▀▒▌
  62. ░▀▄▐▒▀▀▀▀▒▒▒▒▒▒▀▀▀▒▒▒▒▒▒█
  63. ░░░▀▌▒▄██▄▄▄▄████▄▒▒▒▒█▀
  64. ░░░░▄██████████████▒▒▐▌
  65. ░░░▀███▀▀████▀█████▀▒▌
  66. ░░░░░▌▒▒▒▄▒▒▒▄▒▒▒▒▒▒▐
  67. ░░░░░▌▒▒▒▒▀▀▀▒▒▒▒▒▒▒▐*/
  68. //++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++
  69. typedef long long ll;
  70. typedef long double ld;
  71. typedef unsigned long long ull;
  72. //++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++
  73. const ll INF = 1000LL * 1000 * 1000 * 1000 * 1000 * 1000;
  74. const int inf = 1000000000 + 228;
  75. const ld PI = acos(-1.0);
  76. const ll mod1 = inf * inf + 1337 * 42 + 57 * 179 + 228;
  77. const ll mod2 = inf + 9;
  78. const ll bigmod = 1LL * inf * 100 + 3;
  79. const int MAXN = 10005;
  80. const ld EPS = 1e-10;
  81. const int N = 300228;
  82. ll hp = 1e6 + 3;
  83. struct point
  84. {
  85. ld x, y;
  86.  
  87. };
  88.  
  89. struct line
  90. {
  91. ld a,b,c;
  92. };
  93. line getln(point a, point b)
  94. {
  95. line m;
  96. m.a = b.y - a.y;
  97. m.b = a.x - b.x;
  98. m.c = -(m.a * a.x + m.b * a.y);
  99. return m;
  100. }
  101. ld det(ld a, ld b, ld c, ld d)
  102. {
  103. return a * d - b * c;
  104. }
  105. point intersect(line m, line n)
  106. {
  107.  
  108. ld zn = det(m.a, m.b, n.a, n.b);
  109. if (abs(zn) < EPS)
  110. {
  111. return { inf, inf };
  112. }
  113. point res;
  114. res.x = -det(m.c, m.b, n.c, n.b) / zn;
  115. res.y = -det(m.a, m.c, n.a, n.c) / zn;
  116. return res;
  117. }
  118. ld hypot(point a, point b)
  119. {
  120. return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
  121. }
  122. bool belong(point a, point b, point c)
  123. {
  124. return abs(hypot(a, b) - hypot(a, c) - hypot(b, c)) < EPS;
  125. }
  126. bool operator==(point a, point b)
  127. {
  128. return abs(a.x - b.x) < EPS && abs(a.y - b.y) < EPS;
  129. }
  130. bool kekkek(line a, line b)
  131. {
  132. return abs(det(a.a, a.b, b.a, b.b)) < EPS && abs(det(a.b, a.c, b.b, b.c)) < EPS && abs(det(a.a, a.c, b.a, b.c)) < EPS;
  133. }
  134. point operator+(point a, point b)
  135. {
  136. return { a.x + b.x, a.y + b.y };
  137. }
  138. point vec(point a, point b)
  139. {
  140. return { b.x - a.x, b.y - a.y };
  141. }
  142. point operator/(point a, ld x)
  143. {
  144. return { a.x / x, a.y / x };
  145. }
  146. ld operator*(point a, point b)
  147. {
  148. return a.x * b.y - a.y* b.x;
  149. }
  150. ld operator%(point a, point b)
  151. {
  152. return a.x * b.x + a.y * b.y;
  153. }
  154. bool help(point a, vector<point > b)
  155. {
  156. ld sum = 0;
  157. for (int i = 0; i < b.size(); ++i)
  158. {
  159. point x = b[i];
  160. point y = b[(i + 1) % b.size()];
  161. if (a == x || belong(x, y, a))
  162. {
  163. return 1;
  164. }
  165. sum += atan2(vec(a, x) * vec(a, y), vec(a, x) % vec(a, y));
  166. }
  167. return abs(abs(sum) - 2 * PI) < EPS ;
  168. }
  169. bool check(point a, point b, vector<point> kek)
  170. {
  171. point mid = (a + b) / 2;
  172. if (help(mid, kek)) return 0;
  173. line fs = getln(a, b);
  174. for (int i = 0; i < kek.size(); ++i)
  175. {
  176. point ka = kek[i];
  177. point now = kek[(i + 1) % kek.size()];
  178. line ss = getln(ka, now);
  179. point x = intersect(ss, fs);
  180. if (kekkek(fs, ss) && (belong(a,b,ka) && belong(a,b,now))) return 0;
  181. if (x == ka || x == now)
  182. {
  183. continue;
  184. }
  185. if (belong(ka, now, x) && belong(a,b,x))
  186. {
  187. return 0;
  188. }
  189. }
  190. return 1;
  191. }
  192. signed main()
  193. {
  194. fastio();
  195. int n;
  196. cin >> n;
  197. vector<point> a(n);
  198. for (int i = 0; i < n; ++i)
  199. {
  200. cin >> a[i].x >> a[i].y;
  201. }
  202. int m;
  203. cin >> m;
  204. vector<point> x(m);
  205. for (int i = 0; i < m; ++i)
  206. {
  207. cin >> x[i].x >> x[i].y;
  208. }
  209. vector<vector<ld>> d(n + m, vector<ld>(n + m, inf));
  210. for (int i = 0; i < n + m; ++i) d[i][i] = 0;
  211. for (int i = m; i < n + m - 1; ++i)
  212. {
  213. d[i][i + 1] = d[i + 1][i] = hypot(a[i - m], a[i - m + 1]);
  214. }
  215. d[n + m - 1][m] = d[m][n + m - 1] = hypot(a[n - 1], a[0]);
  216. for (int i = 0; i < m; ++i)
  217. {
  218. for (int j = m; j < n + m; ++j)
  219. {
  220. if (check(x[i], a[j - m], a))
  221. {
  222. d[i][j] = d[j][i] = hypot(x[i], a[j - m]);
  223. }
  224. }
  225. }
  226. for (int i = m; i < n + m; ++i)
  227. {
  228. for (int j = m; j < n + m; ++j)
  229. {
  230. if (i == m && j == m + 2 )
  231. {
  232. cout << "";
  233. }
  234. if (i == m + 2 && j == m)
  235. {
  236. cout << "";
  237. }
  238. if (check(a[i - m], a[j - m], a))
  239. {
  240. d[i][j] = d[j][i] = hypot(a[i - m], a[j - m]);
  241. }
  242. }
  243. }
  244. for (int i = 0; i < m; ++i)
  245. {
  246. for (int j = 0; j < m; ++j)
  247. {
  248. if (check(x[i], x[j], a))
  249. {
  250. d[i][j] = d[j][i] = hypot(x[i], x[j]);
  251. }
  252. }
  253. }
  254. /*
  255. for (int i = 0; i < n + m; ++i)
  256. {
  257. for (int j = 0; j < n + m; ++j)
  258. {
  259. cout << d[i][j] << ' ';
  260. }
  261.  
  262. cout << endl;
  263.  
  264. }
  265. sp;*/
  266. for (int k = 0; k < n + m;++k)
  267. {
  268. for (int i = 0; i < n + m; ++i)
  269. {
  270. for (int j = 0; j < n + m; ++j)
  271. {
  272. if (i == 0 && j == 5)
  273. {
  274. cout << "";
  275. }
  276. if (d[i][k] + d[k][j] - EPS < d[i][j])
  277. {
  278. d[i][j] = d[i][k] + d[k][j];
  279. }
  280. }
  281. }
  282. }
  283. ld ans = 0;
  284. //cout << endl;
  285. /*for (int i = 0; i < n + m; ++i)
  286. {
  287. for (int j = 0; j < n + m; ++j)
  288. {
  289. cout << d[i][j] << ' ';
  290. }
  291.  
  292. cout << endl;
  293.  
  294. }
  295. sp;
  296. for (int i = 0; i < m; ++i)
  297. {
  298. for (int j = 0; j < m; ++j)
  299. {
  300. cout << d[i][j] << ' ';
  301. }
  302. cout << endl;
  303. }
  304. sp;*/
  305. for (int i = 0; i < m; ++i)
  306. {
  307. for (int j = 0; j < m; ++j)
  308. {
  309. if (d[i][j] + EPS > ans)
  310. {
  311. ans = d[i][j];
  312. }
  313. }
  314. }
  315. cout << fixed << setprecision(20) << ans;
  316. //sp;
  317. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement