【题解】[JSOI2007] 合金 计算几何+Floyd BZOJ – 1027

题目链接

终于知道什么叫做 “你知道怎么做但就是做不对” 了

首先物品三个属性加起来等于 1，那就有一个属性是废物

这样每个物品就是两个属性，分别代表 $x, y$放到平面上

一堆原料能表示的合金就是这些原料构成的凸包内的所有点

问题就变成了选定一个凸包使得它包含了客户需要的合金的凸包且选定的凸包点数最少

那就判断任意两点 $i, j$构成的向量 $\vec {ij}$，如果所有的点都在其逆时针方向半平面中（其实顺时针也行），则说明它可以作为凸包的边，那就从点 $i$向点 $j$连一条长度为 $1$的有向边，最后整个图的最小环就是答案了，最小环可以用 Floyd 求

问题看似很简单，但需要注意：

• 很多点位置重合
• 客户合金在向量直线上不在线段上
• $m, n$输入别搞反了

#include <bits/stdc++.h>

#define NS (505)
#define eps (1e-7)

using namespace std;

int n, m, dis[NS][NS];

struct vec
{
    double x, y;
    vec() {x = y = 0;}
    vec(double a, double b) {x = a, y = b;}
    void input() {scanf("%lf%lf", &x, &y);}
    vec operator - (const vec oth) const
    {
        return vec(x - oth.x, y - oth.y);
    }
    double crs(vec oth) const {return x * oth.y - y * oth.x;}
    double dot(vec oth) const {return x * oth.x + y * oth.y;}
} P[NS], Q[NS];

int main(int argc, char const* argv[])
{
    memset(dis, 127, sizeof(dis)), scanf("%d%d", &m, &n);
    double noUse;
    for (int i = 1; i <= m; i += 1) P[i].input(), scanf("%lf", &noUse);
    for (int i = 1; i <= n; i += 1) Q[i].input(), scanf("%lf", &noUse);
    for (int i = 1; i <= m; i += 1)
        for (int j = 1; j <= m; j += 1)
        {
            for (int k = 1; k <= n; k += 1)
            {
                double crs = (P[i] - Q[k]).crs(P[j] - Q[k]);
                if (crs > eps) goto end;
                if (fabs(crs) < eps && (P[i] - Q[k]).dot(P[j] - Q[k]) > eps)
                    goto end;
            }
            dis[i][j] = 1;
            end : continue;
        }
    for (int k = 1; k <= m; k += 1)
        for (int i = 1; i <= m; i += 1) if (dis[i][k] < 2e9)
            for (int j = 1; j <= m; j += 1) if (dis[k][j] < 2e9)
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
    int ans = INT_MAX;
    for (int i = 1; i <= m; i += 1) ans = min(ans, dis[i][i]);
    printf("%d\n", ans > 2e9 ? -1 : ans);
    return 0;
}