Advertisement
K_Y_M_bl_C

Untitled

Jan 20th, 2017
91
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.25 KB | None | 0 0
  1. int n, m;
  2. vector <Point> a, b;
  3.  
  4. double distanceToSegment(Point a, Point b, Point c)
  5. {
  6.     Point vab = b - a;
  7.     Point vac = c - a;
  8.     if (vab % vac <= 0)
  9.         return c.distancetoPoint(a);
  10.     Point vba = a - b;
  11.     Point vbc = c - b;
  12.     if (vba % vbc <= 0)
  13.         return c.distancetoPoint(b);
  14.     Line l = Line(a, b);
  15.     return abs(l.distanceFromPoint(c));
  16. }
  17.  
  18. ll sqrdst(Point a, Point b)
  19. {
  20.     return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
  21. }
  22.  
  23. /*
  24.     CASE 1           CASE 2           CASE 3
  25.     .A......         ......A.         \.......
  26.  val/-\-----      val-----/-\         .\...../
  27.     ...\.../         \.../...         ..\.../.
  28.     ....\./.         .\./....         ...\./..
  29.     .....V..         ..V.....         ....V...
  30.     d[0] < d[1]      d[0] > d[1]      d[0] > d[1] && d[lst] > d[lst - 1]
  31. */
  32.  
  33.  
  34. int search(int x, int CASE, double val)
  35. {
  36.     if (CASE == 1)
  37.     {
  38.         int id = 0;
  39.         double ans = a[x].sqrdst(b[0]);
  40.         int l = 0, r = m - 1;
  41.         while (r - l > 1)
  42.         {
  43.             int MID = l + r >> 1;
  44.             double nval = a[x].sqrdst(b[MID]);
  45.             if (nval >= val)
  46.                 l = MID;
  47.             else
  48.             {
  49.                 double nxtval = a[x].sqrdst(b[MID + 1]);
  50.                 if (nval >= nxtval)
  51.                     l = MID;
  52.                 else
  53.                     r = MID;
  54.             }
  55.         }
  56.         for (int i = l; i <= r; ++i)
  57.             if (ans > a[x].sqrdst(b[i]))
  58.                 ans = a[x].sqrdst(b[i]), id = i;
  59.         return id;
  60.     }
  61.     if (CASE == 2)
  62.     {
  63.         int id = 0;
  64.         double ans = a[x].sqrdst(b[0]);
  65.         int l = 0, r = m - 1;
  66.         while (r - l > 1)
  67.         {
  68.             int MID = l + r >> 1;
  69.             double nval = a[x].sqrdst(b[MID]);
  70.             if (nval >= val)
  71.                 r = MID;
  72.             else
  73.             {
  74.                 double nxtval = a[x].sqrdst(b[MID + 1]);
  75.                 if (nval >= nxtval)
  76.                     l = MID;
  77.                 else
  78.                     r = MID;
  79.             }
  80.         }
  81.         for (int i = l; i <= r; ++i)
  82.             if (ans > a[x].sqrdst(b[i]))
  83.                 ans = a[x].sqrdst(b[i]), id = i;
  84.         return id;
  85.     }
  86.     if (CASE == 3)
  87.     {
  88.         int l = 0, r = m - 1;
  89.         while (r - l > 3)
  90.         {
  91.             int m1 = l + (r - l) / 3;
  92.             int m2 = r - (r - l) / 3;
  93.             if (a[x].sqrdst(b[m1]) < a[x].sqrdst(b[m2]))
  94.                 r = m2;
  95.             else
  96.                 l = m2;
  97.         }
  98.         int id = l;
  99.         double ans = a[x].sqrdst(b[l]);
  100.         for (int i = l + 1; i <= r; ++i)
  101.             if (ans > a[x].sqrdst(b[i]))
  102.                 ans = a[x].sqrdst(b[i]), id = i;
  103.         return id;
  104.     }
  105. }
  106.  
  107. double get()
  108. {
  109.     double ans = LINF;
  110.     if ((ll)n * (ll)m >= 1e6)
  111.     {
  112.         forn(i, n)
  113.         {
  114.             double d0 = a[i].sqrdst(b[0]);
  115.             double d1 = a[i].sqrdst(b[1]);
  116.             double dm = a[i].sqrdst(b.back());
  117.             double dm1 = a[i].sqrdst(b[m - 2]);
  118.             bool cs1 = d0 <= d1;
  119.             bool cs2 = d0 >= d1;
  120.             bool cs3 = d0 >= d1 && dm1 <= dm;
  121.             int id;
  122.             if (cs3)
  123.                 id = search(i, 3, 228);
  124.             else
  125.                 if (cs1)
  126.                     id = search(i, 1, d0);
  127.                 else
  128.                     id = search(i, 2, dm);
  129.             int id1 = (id + m - 1) % m;
  130.             if (a[i].sqrdst(b[id1]) > a[i].sqrdst(b[(id + 1) % m]))
  131.                 id1 = (id + 1) % m;
  132.             ans = min(ans, distanceToSegment(b[id], b[id1], a[i]));
  133.         }
  134.     }
  135.     else
  136.     {
  137.         forn(i, n)
  138.         {
  139.             forn(j, m)
  140.                 ans = min(ans, distanceToSegment(b[j], b[(j + 1) % m], a[i]));
  141.         }
  142.     }
  143.     return ans;
  144. }
  145.  
  146. int solve()
  147. {
  148.     scanf("%d", &n);
  149.     a.resize(n);
  150.     forn(i, n)
  151.         scanf("%lf %lf", &a[i].x, &a[i].y);
  152.     scanf("%d", &m);
  153.     b.resize(m);
  154.     forn(i, m)
  155.         scanf("%lf %lf", &b[i].x, &b[i].y);
  156.     double ans = get();
  157.     swap(a, b);
  158.     swap(n, m);
  159.     ans = min(ans, get());
  160.     cout.precision(15);
  161.     cout << fixed << ans;
  162.     return 0;
  163. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement