题解 P4049 【[JSOI2007]合金】

s_r_f · 2020-09-04 20:56:04 · 题解

首先，材料的前两个属性可以唯一确定一个材料，合金的前两个树形也可以唯一确定一个材料。

那么材料和合金都可以被看成平面上的点(a_i,b_i)或(d_i,e_i)

不难发现，一些材料能表示出一种合金当且仅当这个合金（在平面上的点）在选取的材料（在平面上的点）组成的凸包内。

不难发现，选取的点凸包上的边一定满足：所有的合金代表的点都在这条边的某一侧，或者在这条线段上（不是直线上）

那么我们直接求个最小环就行了。

复杂度O(n^3+mn^2).

注意特判答案为 1 或 2 的情况。

#include <bits/stdc++.h>
#define db long double
#define eps 1e-7
using namespace std;
const int N = 505,M = 505;
struct point{
    db x,y;
    point(db xx=0,db yy=0){ x = xx,y = yy; }
    bool operator < (const point w) const{
        if (fabs(x-w.x) > eps) return x < w.x;
        if (fabs(y-w.y) > eps) return y < w.x;
        return 0;
    }
}a[N],b[M];
bool operator == (point a,point b){ return fabs(a.x-b.x) < eps && fabs(a.y-b.y) < eps; }
point operator + (point a,point b){ return point(a.x+b.x,a.y+b.y); }
point operator - (point a,point b){ return point(a.x-b.x,a.y-b.y); }
inline db operator * (point a,point b){ return a.x * b.y - a.y * b.x; }
inline bool left(point a,point b,point p){ return fabs((b-a) * (p-a)) > eps && ((b-a) * (p-a)) > eps;  }
int n,m,dp[N][N],ans;
inline bool check(point p1,point p2){
    if (p1 == p2) return 0;
    for (int i = 1; i <= m; ++i) if (left(p1,p2,b[i])) return 0;
    for (int i = 1; i <= m; ++i) if (fabs((p2-p1)*(b[i]-p1)) < eps){
        if (p1 == b[i] || p2 == b[i]) continue;
        db l,r;
        l = p1.x,r = p2.x; if (l > r) swap(l,r); if (l-eps > b[i].x || b[i].x > r+eps) return 0;
        l = p1.y,r = p2.y; if (l > r) swap(l,r); if (l-eps > b[i].y || b[i].y > r+eps) return 0;
    }
    return 1;
}
int main(){
    int i,j,k;
    cin >> n >> m;
    for (i = 1; i <= n; ++i) cin >> a[i].x >> a[i].y >> a[0].x; sort(a+1,a+n+1);
    for (i = 1; i <= m; ++i) cin >> b[i].x >> b[i].y >> a[0].x; sort(b+1,b+m+1);
    for (i = 1; i <= n; ++i) a[i].x *= 1000000,a[i].y *= 1000000;
    for (i = 1; i <= m; ++i) b[i].x *= 1000000,b[i].y *= 1000000;
    n = unique(a+1,a+n+1) - (a+1);
    m = unique(b+1,b+m+1) - (b+1);
    for (i = 1; i <= n; ++i) for (j = 1; j <= n; ++j) dp[i][j] = 10000000;
    ans = 10000000;
    for (i = 1; i <= n; ++i) for (j = 1; j <= n; ++j)
        if (i != j && check(a[i],a[j])) dp[i][j] = 1;
    for (k = 1; k <= n; ++k) for (i = 1; i <= n; ++i) for (j = 1; j <= n; ++j)
        dp[i][j] = min(dp[i][j],dp[i][k] + dp[k][j]);
    for (i = 1; i <= n; ++i) ans = min(ans,dp[i][i]);
    if (n == 1 && m == 1 && a[1] == b[1]) ans = 1;
    if (ans > n) cout << -1 << '\n'; else cout << ans << '\n';
    return 0;
}