Advertisement
Guest User

Untitled

a guest
Feb 23rd, 2012
100
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.59 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <iostream>
  3. #include <algorithm>
  4. #include <vector>
  5. #include <string>
  6. #include <queue>
  7. #include <map>
  8. #include <set>
  9. #include <cmath>
  10. #include <sstream>
  11. #include <cstring>
  12.  
  13. #define pb push_back
  14. #define mp make_pair
  15. #define PI 3.14159265358979
  16. #define sqr(x) (x)*(x)
  17. #define forn(i, n) for(int i = 0; i < n; ++i)
  18. #define ALL(x) x.begin(), x.end()
  19. #define sz(x) int((x).size())
  20. #define X first
  21. #define Y second
  22. typedef long long ll;
  23. typedef long double ld;
  24. using namespace std;
  25. typedef pair<int,int> pii;
  26. const int INF = 2147483647;
  27. const ll LLINF = 9223372036854775807LL;
  28. const int maxn = 310;
  29. const int maxt = 1010;
  30. int xx[maxn], yy[maxn];
  31. int mx[maxt], my[maxt];
  32. double d[maxn][maxn] = {};
  33. bool good[maxn][maxn] = {};
  34. int main()
  35. {
  36. #ifndef ONLINE_JUDGE
  37.     freopen("mines.in", "r", stdin);
  38.     freopen("mines.out", "w", stdout);
  39. #endif
  40.     int n, k; scanf("%d%d", &n, &k);
  41.     memset(good, 0, sizeof(good));
  42.     for (int i = 0; i < n; ++i) scanf("%d%d", &xx[i], &yy[i]);
  43.     for (int i = 0; i < k; ++i) scanf("%d%d", &mx[i], &my[i]);
  44.     const double cinf = 1e10;
  45.     for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) d[i][j] = cinf*(i!=j);
  46.     double best = cinf;
  47.     for (int i = 0; i < n; ++i)
  48.         for (int j = i+1; j < n; ++j) {
  49.             bool ok = true;
  50.             for (int t = 0; t < k; ++t) {
  51.                 int vx = xx[j]-xx[i];
  52.                 int vy = yy[j]-yy[i];
  53.                 int tx = mx[t]-xx[i];
  54.                 int ty = my[t]-yy[i];
  55.                 int cur = vx*ty-vy*tx;
  56.                 if (cur != 0) ok = false;
  57.                 if (!(vx*tx+vy*ty>=0 && -vx*(mx[t]-xx[j])-vy*(my[t]-yy[j])>=0)) ok = false;
  58.             }
  59.             double curd = sqrt(0.+sqr(xx[i]-xx[j])+sqr(yy[i]-yy[j]));
  60.             if (ok) best = min(best, 2*curd);
  61.         }
  62.     for (int i = 0; i < n; ++i)
  63.         for (int j = i+1; j < n; ++j) {
  64.             bool haspos = false;
  65.             bool hasneg = false;
  66.             for (int t = 0; t < k; ++t) {
  67.                 int vx = xx[j]-xx[i];
  68.                 int vy = yy[j]-yy[i];
  69.                 int tx = mx[t]-xx[i];
  70.                 int ty = my[t]-yy[i];
  71.                 int cur = vx*ty-vy*tx;
  72.                 if (cur > 0) haspos = true;
  73.                 if (cur < 0) hasneg = true;
  74.             }
  75.             if (haspos && hasneg) continue;
  76.             double curd = sqrt(0.+sqr(xx[i]-xx[j])+sqr(yy[i]-yy[j]));
  77.             if (haspos) d[i][j] = curd, good[i][j] = 1;
  78.             if (hasneg) d[j][i] = curd, good[j][i] = 1;
  79.         }
  80.     for (int t = 0; t < n; ++t)
  81.         for (int i = 0; i < n; ++i)
  82.             for (int j = 0; j < n; ++j) {
  83.                 if (d[i][j] > d[i][t]+d[t][j]) {
  84.                     d[i][j] = d[i][t]+d[t][j];
  85.                 }
  86.             }
  87.    
  88.     for (int i = 0; i < n; ++i)
  89.         for (int j = 0; j < n; ++j) {
  90.             if (good[i][j]) {
  91.                 best = min(best, d[i][j]+d[j][i]);
  92.             }
  93.         }
  94.     if (best < cinf) printf("%.10lf\n", best);
  95.     else printf("-1\n");
  96.     return 0;
  97. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement