Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <iostream>
- #include <algorithm>
- #include <vector>
- #include <string>
- #include <queue>
- #include <map>
- #include <set>
- #include <cmath>
- #include <sstream>
- #include <cstring>
- #define pb push_back
- #define mp make_pair
- #define PI 3.14159265358979
- #define sqr(x) (x)*(x)
- #define forn(i, n) for(int i = 0; i < n; ++i)
- #define ALL(x) x.begin(), x.end()
- #define sz(x) int((x).size())
- #define X first
- #define Y second
- typedef long long ll;
- typedef long double ld;
- using namespace std;
- typedef pair<int,int> pii;
- const int INF = 2147483647;
- const ll LLINF = 9223372036854775807LL;
- const int maxn = 310;
- const int maxt = 1010;
- int xx[maxn], yy[maxn];
- int mx[maxt], my[maxt];
- double d[maxn][maxn] = {};
- bool good[maxn][maxn] = {};
- int main()
- {
- #ifndef ONLINE_JUDGE
- freopen("mines.in", "r", stdin);
- freopen("mines.out", "w", stdout);
- #endif
- int n, k; scanf("%d%d", &n, &k);
- memset(good, 0, sizeof(good));
- for (int i = 0; i < n; ++i) scanf("%d%d", &xx[i], &yy[i]);
- for (int i = 0; i < k; ++i) scanf("%d%d", &mx[i], &my[i]);
- const double cinf = 1e10;
- for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) d[i][j] = cinf*(i!=j);
- double best = cinf;
- for (int i = 0; i < n; ++i)
- for (int j = i+1; j < n; ++j) {
- bool ok = true;
- for (int t = 0; t < k; ++t) {
- int vx = xx[j]-xx[i];
- int vy = yy[j]-yy[i];
- int tx = mx[t]-xx[i];
- int ty = my[t]-yy[i];
- int cur = vx*ty-vy*tx;
- if (cur != 0) ok = false;
- if (!(vx*tx+vy*ty>=0 && -vx*(mx[t]-xx[j])-vy*(my[t]-yy[j])>=0)) ok = false;
- }
- double curd = sqrt(0.+sqr(xx[i]-xx[j])+sqr(yy[i]-yy[j]));
- if (ok) best = min(best, 2*curd);
- }
- for (int i = 0; i < n; ++i)
- for (int j = i+1; j < n; ++j) {
- bool haspos = false;
- bool hasneg = false;
- for (int t = 0; t < k; ++t) {
- int vx = xx[j]-xx[i];
- int vy = yy[j]-yy[i];
- int tx = mx[t]-xx[i];
- int ty = my[t]-yy[i];
- int cur = vx*ty-vy*tx;
- if (cur > 0) haspos = true;
- if (cur < 0) hasneg = true;
- }
- if (haspos && hasneg) continue;
- double curd = sqrt(0.+sqr(xx[i]-xx[j])+sqr(yy[i]-yy[j]));
- if (haspos) d[i][j] = curd, good[i][j] = 1;
- if (hasneg) d[j][i] = curd, good[j][i] = 1;
- }
- for (int t = 0; t < n; ++t)
- for (int i = 0; i < n; ++i)
- for (int j = 0; j < n; ++j) {
- if (d[i][j] > d[i][t]+d[t][j]) {
- d[i][j] = d[i][t]+d[t][j];
- }
- }
- for (int i = 0; i < n; ++i)
- for (int j = 0; j < n; ++j) {
- if (good[i][j]) {
- best = min(best, d[i][j]+d[j][i]);
- }
- }
- if (best < cinf) printf("%.10lf\n", best);
- else printf("-1\n");
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement