|
|
楼主 |
发表于 2024-3-16 09:03:45
|
显示全部楼层
- //#include "stdafx.h"
- //#define LOCAL
- #pragma GCC optimize(2)
- #pragma G++ optimize(2)
- #pragma warning(disable:4996)
- //#pragma comment(linker, "/STACK:1024000000,1024000000")
- #include <stdio.h>
- #include <iostream>
- #include <iomanip>
- #include <string>
- #include <ctype.h>
- #include <string.h>
- #include <fstream>
- #include <sstream>
- #include <math.h>
- #include <map>
- //#include <unordered采用map>
- #include <algorithm>
- #include <vector>
- #include <stack>
- #include <queue>
- #include <set>
- #include <time.h>
- #include <stdlib.h>
- #include <bitset>
- using namespace std;
- //#define int unsigned long long
- //#define int long long
- #define re register int
- #define ci const int
- #define ui unsigned int
- typedef pair<int, int> P;
- #define FE(cur) for(re h = head[cur], to; ~h; h = g[h].nxt)
- #define ilv inline void
- #define ili inline int
- #define ilc inline char
- #define ild inline double
- #define ilp inline P
- #define LEN(cur) (hjt[cur].r - hjt[cur].l)
- #define MID(cur) (hjt[cur].l + hjt[cur].r >> 1)
- #define SQUARE(x) ((x) * (x))
- typedef vector<int>::iterator vit;
- typedef set<int>::iterator sit;
- typedef map<int, int>::iterator mit;
- const int inf = ~0u>>1;
- const double PI = acos(-1.0), eps = 1e-8;
- namespace fastio
- {
- const int BUF = 1 << 21;
- char fr[BUF], fw[BUF], *pr1 = fr, *pr2 = fr;int pw;
- ilc gc() { return pr1 == pr2 && (pr2 = (pr1 = fr) + fread(fr, 1, BUF, stdin), *pr2 = 0, pr1 == pr2) ? EOF : *pr1++; }
- ilv flush() { fwrite(fw, 1, pw, stdout); pw = 0; }
- ilv pc(char c) { if (pw >= BUF) flush(); fw[pw++] = c; }
- ili read(int &x)
- {
- x = 0; int f = 1; char c = gc(); if (!~c) return EOF;
- while(!isdigit(c)) { if (c == '-') f = -1; c = gc(); }
- while(isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = gc();
- x *= f; return 1;
- }
- ili read(double &x)
- {
- int xx = 0; double f = 1.0, fraction = 1.0; char c = gc(); if (!~c) return EOF;
- while (!isdigit(c)) { if (c == '-') f = -1.0; c = gc(); }
- while (isdigit(c)) { xx = (xx << 3) + (xx << 1) + (c ^ 48), c = gc(); }
- x = xx;
- if (c ^ '.') { x = f * xx; return 1; }
- c = gc();
- while (isdigit(c)) x += (c ^ 48) * (fraction /= 10), c = gc();
- x *= f; return 1;
- }
- ilv write(int x) { if (x < 0) pc('-'), x = -x; if (x > 9) write(x / 10); pc(x % 10 + 48); }
- ilv writeln(int x) { write(x);pc(10); }
- ili read(char *x)
- {
- char c = gc(); if (!~c) return EOF;
- while(!isalpha(c) && !isdigit(c)) c = gc();
- while (isalpha(c) || isdigit(c)) *x++ = c, c = gc();
- *x = 0; return 1;
- }
- ili readln(char *x)
- {
- char c = gc(); if (!~c) return EOF;
- while(c == 10) c = gc();
- while(c >= 32 && c <= 126) *x++ = c, c = gc();
- *x = 0; return 1;
- }
- ilv write(char *x) { while(*x) pc(*x++); }
- ilv write(const char *x) { while(*x) pc(*x++); }
- ilv writeln(char *x) { write(x); pc(10); }
- ilv writeln(const char *x) { write(x); pc(10); }
- ilv write(char c) { pc(c); }
- ilv writeln(char c) { write(c); pc(10); }
- } using namespace fastio;
- const int maxn = 1e4+5;
- int n, m;
- struct Point
- {
- double x, y;
- Point(double x = 0, double y = 0): x(x), y(y){};
- Point operator - (Point o)
- {
- return Point(x - o.x, y - o.y);
- }
- double operator / (Point o)
- {
- return x * o.y - y * o.x;
- }
- double operator * (Point o)
- {
- return x * o.x + y * o.y;
- }
- Point neg()
- {
- return Point(-x, -y);
- }
- double magnitude()
- {
- return sqrt(SQUARE(x) + SQUARE(y));
- }
- Point scalar(double a)
- {
- return Point(x * a, y *a);
- }
- Point normalize()
- {
- return scalar(1 / magnitude());
- }
- } shape1[maxn], shape2[maxn], d;
- stack<Point> s;
- Point center(Point *shape, int n)
- {
- Point ans;
- for (re i = 0; i < n; i++)
- {
- ans.x += shape[i].x;
- ans.y += shape[i].y;
- }
- ans.x /= n, ans.y /= n;
- return ans;
- }
- Point support1(Point *shape, int n, Point d)
- {
- double mx = -inf, proj;
- Point ans;
- for (re i = 0; i < n; i++)
- {
- proj = shape[i] * d;
- if (mx < proj)
- {
- mx = proj;
- ans = shape[i];
- }
- }
- return ans;
- }
- Point support(Point *shape1, Point *shape2, int n1, int n2, Point d)
- {
- Point x = support1(shape1, n1, d), y = support1(shape2, n2, d.neg());
- return x - y;
- }
- ili dcmp(double x)
- {
- if (fabs(x) < eps) return 0;
- return x < 0 ? -1 : 1;
- }
- Point perp(Point &a, Point &b, Point &c)
- {
- return b.scalar(a * c) - a.scalar(b * c);
- }
- Point closestPointToOrigin(Point &a, Point &b)
- {
- double da = a.magnitude();
- double db = b.magnitude();
- double dis = fabs(a / b) / (a - b).magnitude();
- Point ab = b - a, ba = a - b, ao = a.neg(), bo = b.neg();
- if (ab * ao > 0 && ba * bo > 0) return perp(ab, ao, ab).normalize().scalar(dis);
- return da < db ? a.neg() : b.neg();
- }
- ild gjk(Point *shape1, Point *shape2, int n1, int n2)
- {
- d = center(shape2, n2) - center(shape1, n1);
- Point a = support(shape1, shape2, n1, n2, d);
- Point b = support(shape1, shape2, n1, n2, d.neg());
- Point c, p1, p2;
- d = closestPointToOrigin(a, b);
- s.push(a);
- s.push(b);
- while (1)
- {
- c = support(shape1, shape2, n1, n2, d);
- a = s.top(); s.pop();
- b = s.top(); s.pop();
- double da = d * a, db = d * b, dc = d * c;
- if (!dcmp(dc - da) || !dcmp(dc - db)) return d.magnitude();
- p1 = closestPointToOrigin(a, c);
- p2 = closestPointToOrigin(b, c);
- p1.magnitude() < p2.magnitude() ? s.push(a), d = p1 : s.push(b), d = p2;
- s.push(c);
- }
- }
- signed main()
- {
- #ifdef LOCAL
- FILE *ALLIN = freopen("d:\\data.in", "r", stdin);
- // freopen("d:\\my.out", "w", stdout);
- #endif
- while (read(n), read(m), n + m)
- {
- for (re i = 0; i < n; i++) read(shape1[i].x), read(shape1[i].y);
- for (re i = 0; i < m; i++) read(shape2[i].x), read(shape2[i].y);
- printf("%.5lf\n", gjk(shape1, shape2, n, m));
- }
- flush();
- #ifdef LOCAL
- fclose(ALLIN);
- #endif
- return 0;
- }
- https://cloud.tencent.com/developer/article/1679020?areaId=106001
|
|
发表于 2024-3-16 09:02:01