Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- int n, m;
- vector <Point> a, b;
- double distanceToSegment(Point a, Point b, Point c)
- {
- Point vab = b - a;
- Point vac = c - a;
- if (vab % vac <= 0)
- return c.distancetoPoint(a);
- Point vba = a - b;
- Point vbc = c - b;
- if (vba % vbc <= 0)
- return c.distancetoPoint(b);
- Line l = Line(a, b);
- return abs(l.distanceFromPoint(c));
- }
- ll sqrdst(Point a, Point b)
- {
- return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
- }
- /*
- CASE 1 CASE 2 CASE 3
- .A...... ......A. \.......
- val/-\----- val-----/-\ .\...../
- ...\.../ \.../... ..\.../.
- ....\./. .\./.... ...\./..
- .....V.. ..V..... ....V...
- d[0] < d[1] d[0] > d[1] d[0] > d[1] && d[lst] > d[lst - 1]
- */
- int search(int x, int CASE, double val)
- {
- if (CASE == 1)
- {
- int id = 0;
- double ans = a[x].sqrdst(b[0]);
- int l = 0, r = m - 1;
- while (r - l > 1)
- {
- int MID = l + r >> 1;
- double nval = a[x].sqrdst(b[MID]);
- if (nval >= val)
- l = MID;
- else
- {
- double nxtval = a[x].sqrdst(b[MID + 1]);
- if (nval >= nxtval)
- l = MID;
- else
- r = MID;
- }
- }
- for (int i = l; i <= r; ++i)
- if (ans > a[x].sqrdst(b[i]))
- ans = a[x].sqrdst(b[i]), id = i;
- return id;
- }
- if (CASE == 2)
- {
- int id = 0;
- double ans = a[x].sqrdst(b[0]);
- int l = 0, r = m - 1;
- while (r - l > 1)
- {
- int MID = l + r >> 1;
- double nval = a[x].sqrdst(b[MID]);
- if (nval >= val)
- r = MID;
- else
- {
- double nxtval = a[x].sqrdst(b[MID + 1]);
- if (nval >= nxtval)
- l = MID;
- else
- r = MID;
- }
- }
- for (int i = l; i <= r; ++i)
- if (ans > a[x].sqrdst(b[i]))
- ans = a[x].sqrdst(b[i]), id = i;
- return id;
- }
- if (CASE == 3)
- {
- int l = 0, r = m - 1;
- while (r - l > 3)
- {
- int m1 = l + (r - l) / 3;
- int m2 = r - (r - l) / 3;
- if (a[x].sqrdst(b[m1]) < a[x].sqrdst(b[m2]))
- r = m2;
- else
- l = m2;
- }
- int id = l;
- double ans = a[x].sqrdst(b[l]);
- for (int i = l + 1; i <= r; ++i)
- if (ans > a[x].sqrdst(b[i]))
- ans = a[x].sqrdst(b[i]), id = i;
- return id;
- }
- }
- double get()
- {
- double ans = LINF;
- if ((ll)n * (ll)m >= 1e6)
- {
- forn(i, n)
- {
- double d0 = a[i].sqrdst(b[0]);
- double d1 = a[i].sqrdst(b[1]);
- double dm = a[i].sqrdst(b.back());
- double dm1 = a[i].sqrdst(b[m - 2]);
- bool cs1 = d0 <= d1;
- bool cs2 = d0 >= d1;
- bool cs3 = d0 >= d1 && dm1 <= dm;
- int id;
- if (cs3)
- id = search(i, 3, 228);
- else
- if (cs1)
- id = search(i, 1, d0);
- else
- id = search(i, 2, dm);
- int id1 = (id + m - 1) % m;
- if (a[i].sqrdst(b[id1]) > a[i].sqrdst(b[(id + 1) % m]))
- id1 = (id + 1) % m;
- ans = min(ans, distanceToSegment(b[id], b[id1], a[i]));
- }
- }
- else
- {
- forn(i, n)
- {
- forn(j, m)
- ans = min(ans, distanceToSegment(b[j], b[(j + 1) % m], a[i]));
- }
- }
- return ans;
- }
- int solve()
- {
- scanf("%d", &n);
- a.resize(n);
- forn(i, n)
- scanf("%lf %lf", &a[i].x, &a[i].y);
- scanf("%d", &m);
- b.resize(m);
- forn(i, m)
- scanf("%lf %lf", &b[i].x, &b[i].y);
- double ans = get();
- swap(a, b);
- swap(n, m);
- ans = min(ans, get());
- cout.precision(15);
- cout << fixed << ans;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement