BZOJ1027 [JSOI2007]合金

浏览数：41 / 时间：2015年06月09日

每个物品有三个参量，其实等价于两个，因为总和确定。
于是问题变成二维平面上一堆点，求最小的b的子集形成的凸包，包含这些点a。
用Floyd绕一圈即可。

  1 /**************************************************************
  2     Problem: 1027
  3     User: rausen
  4     Language: C++
  5     Result: Accepted
  6     Time:1136 ms
  7     Memory:1820 kb
  8 ****************************************************************/
  9  
 10 #include <cstdio>
 11 #include <cmath>
 12 #include <algorithm>
 13  
 14 #define P Point
 15 using namespace std;
 16 typedef double lf;
 17 const int N = 505;
 18 const int inf = 1e9;
 19 const lf eps = 1e-8;
 20  
 21 struct Point {
 22     lf x, y;
 23     P() {}
 24     P(lf _x, lf _y) : x(_x), y(_y) {}
 25      
 26     inline bool operator != (const P p) const {
 27         return fabs(x - p.x) > eps || fabs(y - p.y) > eps;
 28     }
 29     inline P operator - (P p) {
 30         return P(x - p.x, y - p.y);
 31     }
 32     inline lf operator * (P p) {
 33         return x * p.y - y * p.x;
 34     }
 35      
 36     inline void read() {
 37         scanf("%lf%lf%*lf", &x, &y);
 38     }
 39 } a[N], b[N];
 40  
 41 int n, m;
 42 int dis[N][N];
 43  
 44 bool in_one_line(P x, P y) {
 45     int i;
 46     if (x.x > y.x) swap(x, y);
 47     for (i = 1; i <= m; ++i)
 48         if (b[i].x < x.x || b[i].x > y.x) return 0;
 49     if (x.y > y.y) swap(x, y);
 50     for (i = 1; i <= m; ++i)
 51         if (b[i].y < x.y || b[i].y > y.y) return 0;
 52     return 1;
 53 }
 54  
 55 int check(P x, P y) {
 56     int i, cnt1, cnt2;
 57     lf tmp;
 58     for (i = 1, cnt1 = cnt2 = 0; i <= m; ++i) {
 59         tmp = (y - x) * (b[i] - x);
 60         if (tmp > eps) ++cnt1;
 61         if (tmp < -eps) ++cnt2;
 62         if (cnt1 && cnt2) return 0;
 63     }
 64     if (!cnt1 && !cnt2 && in_one_line(x, y)) {
 65         puts("2");
 66         return -1;
 67     }
 68     return cnt1 ? 1 : cnt2 ? 2 : 3;
 69 }
 70  
 71 void Floyd() {
 72     int ans = inf, i, j, k;
 73     for (k = 1; k <= n; ++k)
 74         for (i = 1; i <= n; ++i)
 75             for (j = 1; j <= n; ++j)
 76                 dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
 77     for (i = 1; i <= n; ++i)
 78         ans = min(ans, dis[i][i]);
 79     if (ans == inf || ans <= 2) puts("-1");
 80     else printf("%d\n", ans);
 81 }
 82  
 83 void solve() {
 84     int i, j, f;
 85     for (i = 1; i <= n; ++i)
 86         for (j = 1; j <= n; ++j)
 87             dis[i][j] = inf;
 88     for (i = 1; i <= n; ++i)
 89         for (j = i + 1; j <= n; ++j) {
 90             f = check(a[i], a[j]);
 91             if (f == -1) return;
 92             if (f == 1) dis[i][j] = 1;
 93             else if (f == 2) dis[j][i] = 1;
 94             else if (f == 3) dis[i][j] = dis[j][i] = 1;
 95         }
 96     Floyd();
 97 }
 98  
 99 bool special_judge() {
100     int i;
101     for (i = 1; i <= n; ++i)
102         if (a[1] != a[i]) return 0;
103     for (i = 1; i <= m; ++i)
104         if (a[1] != b[i]) return 0;
105     puts("1");
106     return 1;
107 }
108  
109 int main() {
110     int i;
111     scanf("%d%d", &n, &m);
112     for (i = 1; i <= n; ++i)
113         a[i].read();
114     for (i = 1; i <= m; ++i)
115         b[i].read();
116     if (special_judge()) return 0;
117     solve();
118     return 0;
119 }