fork download
  1. #include <bits/stdc++.h>
  2. #define X first
  3. #define Y second
  4. using namespace std;
  5.  
  6. typedef long double ld;
  7. typedef pair<ld, ld> pt;
  8. typedef pair<pt, ld> hp;
  9.  
  10. pt ct;
  11. bool f;
  12.  
  13. ld dis(pt a, pt b) {
  14. return hypot(a.X - b.X, a.Y - b.Y);
  15. }
  16.  
  17. ld ccw(pt a, pt b, pt c) {
  18. return (b.X - a.X) * (c.Y - a.Y) - (b.Y - a.Y) * (c.X - a.X);
  19. }
  20.  
  21. ld cp(pt a, pt b) {
  22. return a.X * b.Y - a.Y * b.X;
  23. }
  24.  
  25. bool cmp(hp h1, hp h2) {
  26. ld c = ccw(ct, h1.X, h2.X);
  27. bool f1 = h1.X > ct, f2 = h2.X > ct;
  28. if(f1 != f2)
  29. return f1 > f2;
  30. return fabsl(c) < 1e-9 ? h1.Y * dis(ct, h2.X) < h2.Y * dis(ct, h1.X) : c > 1e-9;
  31. }
  32.  
  33. bool inside(vector<pt> &v, pt p) {
  34. int n = v.size(), st = 1, ed, mi;
  35. if(ccw(v[0], v[n - 1], p) > 1e-9 || ccw(v[0], v[1], p) < -1e-9)
  36. return false;
  37. ed = n - 1;
  38. while(st + 1 < ed) {
  39. mi = (st + ed) / 2;
  40. ccw(v[0], v[mi], p) > 1e-9 ? st = mi : ed = mi;
  41. }
  42. return ccw(v[st], p, v[st + 1]) < 1e-9;
  43. }
  44.  
  45. pt isc(hp h1, hp h2) {
  46. double a = cp(h1.X, h2.X);
  47. pt tmp;
  48. tmp.X = (h1.Y * h2.X.Y - h1.X.Y * h2.Y) / a;
  49. tmp.Y = (h1.X.X * h2.Y - h1.Y * h2.X.X) / a;
  50. return tmp;
  51. }
  52.  
  53. bool chk(hp h1, hp h2, hp h3) {
  54. pt tmp;
  55. if(cp(h2.X, h3.X) < 1e-9)
  56. return false;
  57. tmp = isc(h2, h3);
  58. return h1.X.X * tmp.X + h1.X.Y * tmp.Y > h1.Y + 1e-9;
  59. }
  60.  
  61. vector<pt> hpisc(vector<hp>& tv) {
  62. vector<pt> rv;
  63. int m;
  64. deque<hp> dq;
  65. sort(tv.begin(), tv.end(), cmp);
  66. for(auto i : tv) {
  67. while(dq.size() > 1 && chk(i, dq[dq.size() - 2], dq.back()))
  68. dq.pop_back();
  69. while(dq.size() > 1 && chk(dq[1], i, dq.front()))
  70. dq.pop_front();
  71. if(dq.size() && fabsl(cp(dq.back().X, i.X)) < 1e-9)
  72. continue;
  73. dq.push_back(i);
  74. }
  75. while(dq.size() > 2 && chk(dq.front(), dq[dq.size() - 2], dq.back()))
  76. dq.pop_back();
  77. while(dq.size() > 2 && chk(dq[1], dq.back(), dq.front()))
  78. dq.pop_front();
  79. m = dq.size();
  80. for(int i = 0; i < m; i++) {
  81. if(cp(dq[i].X, dq[(i + 1) % m].X) < 1e-9)
  82. continue;
  83. rv.push_back(isc(dq[i], dq[(i + 1) % m]));
  84. }
  85. return rv;
  86. }
  87.  
  88. ld hparea(vector<pt> p, vector<pt> p2, pt vc, pt vc2, ld tm) {
  89. int n = p.size(), m = p2.size(), sz;
  90. ld tr = 0;
  91. bool f2 = false, f3 = false;
  92. vector<pt> v;
  93. vector<hp> hv;
  94. for(int i = 0; i < n; i++) {
  95. p[i].X += vc.X * tm;
  96. p[i].Y += vc.Y * tm;
  97. }
  98. for(int i = 0; i < m; i++) {
  99. p2[i].X += vc2.X * tm;
  100. p2[i].Y += vc2.Y * tm;
  101. }
  102. hv.resize(n + m);
  103. for(int i = 0; i < n; i++) {
  104. hv[i].X.X = p[(i + 1) % n].Y - p[i].Y;
  105. hv[i].X.Y = p[i].X - p[(i + 1) % n].X;
  106. hv[i].Y = hv[i].X.X * p[i].X + hv[i].X.Y * p[i].Y;
  107. }
  108. for(int i = 0; i < m; i++) {
  109. hv[i + n].X.X = p2[(i + 1) % m].Y - p2[i].Y;
  110. hv[i + n].X.Y = p2[i].X - p2[(i + 1) % m].X;
  111. hv[i + n].Y = hv[i + n].X.X * p2[i].X + hv[i + n].X.Y * p2[i].Y + dis(p2[i], p2[(i + 1) % m]) * 1e-3;
  112. }
  113. v = hpisc(hv);
  114. sz = v.size();
  115. for(int i = 0; i < sz; i++)
  116. tr += v[i].X * v[(i + 1) % sz].Y - v[i].Y * v[(i + 1) % sz].X;
  117. tr = fabsl(tr) / 2;
  118. for(int i = 0; i < n; i++) {
  119. if(inside(p2, p[i])) {
  120. f2 = true;
  121. break;
  122. }
  123. }
  124. for(int i = 0; i < m; i++) {
  125. if(inside(p, p2[i])) {
  126. f3 = true;
  127. break;
  128. }
  129. }
  130. if(!f2 && !f3) {
  131. sz = 0;
  132. tr = 0;
  133. return tr;
  134. }
  135. if(sz && fabsl(tr) < 1e-9)
  136. f = true;
  137. return tr;
  138. }
  139.  
  140. int main() {
  141. int n, m, cnt = 50;
  142. ld r, r2, s = 0, e = 3, mi, mi2, rmax = 0;
  143. pt vc, vc2;
  144. vector<pt> p, p2;
  145. scanf("%d", &n);
  146. p.resize(n);
  147. for(int i = 0; i < n; i++)
  148. scanf("%Lf %Lf", &p[i].X, &p[i].Y);
  149. reverse(p.begin(), p.end());
  150. scanf("%Lf %Lf %d", &vc.X, &vc.Y, &m);
  151. p2.resize(m);
  152. for(int i = 0; i < m; i++)
  153. scanf("%Lf %Lf", &p2[i].X, &p2[i].Y);
  154. reverse(p2.begin(), p2.end());
  155. scanf("%Lf %Lf", &vc2.X, &vc2.Y);
  156. if(fabsl(dis(vc, vc2)) < 1e-9) {
  157. printf("never");
  158. return 0;
  159. }
  160. while(cnt--) {
  161. mi = (s * 2 + e) / 3;
  162. mi2 = (s + e * 2) / 3;
  163. f = false;
  164. r = hparea(p, p2, vc, vc2, mi);
  165. if(f)
  166. r = 1e-9;
  167. f = false;
  168. r2 = hparea(p, p2, vc, vc2, mi2);
  169. if(f)
  170. r2 = 1e-9;
  171. rmax = max(rmax, max(r, r2));
  172. r > r2 - 1e-9 ? e = mi2 : s = mi;
  173. printf("%.3Lf %.12Lf %.3Lf %.12Lf\n", mi, r, mi2, r2);
  174. }
  175. if(fabsl(rmax) < 1e-9)
  176. printf("never");
  177. else
  178. printf("%.9Lf", s);
  179. return 0;
  180. }
Success #stdin #stdout 0s 5304KB
stdin
3 0 0 1 1 2 0 0 0
3 2 1 0 2 2 2 -1 0
stdout
1.000 0.000001284701 2.000 0.000000000000
0.667 0.000000000000 1.333 0.000000000000
0.444 0.000000000000 0.889 0.000000000000
0.296 0.000000000000 0.593 0.000000000000
0.198 0.000000000000 0.395 0.000000000000
0.132 0.000000000000 0.263 0.000000000000
0.088 0.000000000000 0.176 0.000000000000
0.059 0.000000000000 0.117 0.000000000000
0.039 0.000000000000 0.078 0.000000000000
0.026 0.000000000000 0.052 0.000000000000
0.017 0.000000000000 0.035 0.000000000000
0.012 0.000000000000 0.023 0.000000000000
0.008 0.000000000000 0.015 0.000000000000
0.005 0.000000000000 0.010 0.000000000000
0.003 0.000000000000 0.007 0.000000000000
0.002 0.000000000000 0.005 0.000000000000
0.002 0.000000000000 0.003 0.000000000000
0.001 0.000000000000 0.002 0.000000000000
0.001 0.000000000000 0.001 0.000000000000
0.000 0.000000000000 0.001 0.000000000000
0.000 0.000000000000 0.001 0.000000000000
0.000 0.000000000000 0.000 0.000000000000
0.000 0.000000000000 0.000 0.000000000000
0.000 0.000000000000 0.000 0.000000000000
0.000 0.000000000000 0.000 0.000000000000
0.000 0.000000000000 0.000 0.000000000000
0.000 0.000000000000 0.000 0.000000000000
0.000 0.000000000000 0.000 0.000000000000
0.000 0.000000000000 0.000 0.000000000000
0.000 0.000000000000 0.000 0.000000000000
0.000 0.000000000000 0.000 0.000000000000
0.000 0.000000000000 0.000 0.000000000000
0.000 0.000000000000 0.000 0.000000000000
0.000 0.000000000000 0.000 0.000000000000
0.000 0.000000000000 0.000 0.000000000000
0.000 0.000000000000 0.000 0.000000000000
0.000 0.000000000000 0.000 0.000000000000
0.000 0.000000000000 0.000 0.000000000000
0.000 0.000000000000 0.000 0.000000000000
0.000 0.000000000000 0.000 0.000000000000
0.000 0.000000000000 0.000 0.000000000000
0.000 0.000000000000 0.000 0.000000000000
0.000 0.000000000000 0.000 0.000000000000
0.000 0.000000000000 0.000 0.000000000000
0.000 0.000000000000 0.000 0.000000000000
0.000 0.000000000000 0.000 0.000000000000
0.000 0.000000000000 0.000 0.000000000000
0.000 0.000000000000 0.000 0.000000000000
0.000 0.000000000000 0.000 0.000000000000
0.000 0.000000000000 0.000 0.000000000000
0.000000000