【题解】P4049 [JSOI2007]合金

模型转换+计算几何基础好题。

题意

直接上传送门

模型转换

首先我们发现，由于三个属性的和恒为$1$，那么实际上第三个属性并没有什么用。于是我们可以只用两个属性描述一个物品，那么就可以把物品放在二维平面上，当做一堆点来处理。

接下来有一个神奇的结论~~（我还是不知道如何证明）~~:

对于两个点（也可以当做向量），在本题中能由这两个物品构成的点一定在以这两个点为端点的线段上。

推广（感性理解）一下，由一堆物品可以构成的点，一定在这一堆物品构成的凸多边形内。

那就好办了，题意就转化为了有$m$个可选点和$n$个定点，要求从$m$个可选点中选出数量最少的点，使这些点构成的凸多边形能够完全包含$n$个定点。

如上图，六个可选点（红色）中我们只要选择四个就可以包含所有定点（蓝色）。

那么我们就可以接着转换模型，我们先观察凸包的边的性质：对于每一条凸包上的边，所有的定点都在这条线段所在直线的同侧。于是我们可以按照一定的顺序，在一些点之间连边。比如我们按照顺时针顺序连单向边，如果当前点和下一个点（要判断是否重合，可以用点积和叉积）构成的线段满足所有的定点都在这条线段同侧（同时要判断在凸包内还是外，可以用叉积），就连一条权值为$1$的边，最后用$Floyd$跑一遍最小环即可。

还是上面那个例子，我们可以看到按照上述规则建完图后的样子，显然最小环为$4$。

实现细节

我们上面说到要判断点是否重合，那么我们就可以用点积和叉积配合实现。（熟练掌握的巨佬可以直接跳过）

先搬一些基础知识（详见洛谷日报）

向量的数量积，也叫点积、内积，几何意义为一个向量在另一个向量上的投影再乘上第二个向量的模长。 $a$ 与 $b$的数量积表示为 $a\cdot b$ ，是一个实数。计算式为 $a\cdot b=\left|a\right|\left|b\right|\cos \theta (\theta =⟨a,b⟩)$（ $\theta$ 表示 $a$,$b$ 的夹角）。引入坐标后，通过三角恒等变换的推导，对于 $a=(x_1,y_1)$,$b=(x_2,y_2)$, $a\cdot b=x_1{x}_2+y_1{y}_2$ 。

如果两个向量同向（共线），那么它们的数量积为他们的模长之积。如果两个向量夹角 $<90^{\circ }$∘ ，那么它们的数量积为正。如果两个向量夹角 $=90^{\circ }$∘ ，那么他们的数量积为 $0$ ，因为$\cos 90^{\circ }=0$。如果两个向量夹角 $>90^{\circ }$ ，那么它们的数量积为负。如果两个向量反向（共线），那么它们的数量积为他们的模长之积的相反数。

向量的外积，也叫叉积，几何意义是两向量由平行四边形法则围成的面积。外积是一个向量，垂直于原来两个向量所在的平面。对于$a=(x_1,y_1),b=(x_2,y_2)$, $a\times b$方向就要用右手从 $a$ 沿着不大于平角的方向旋转，大拇指的方向就是外积的方向。如果外积方向朝外，那么值为正，否则值为负。计算式为 $a\times b=|a||b|\sin \theta =x_1{y}_2-x_2{y}_1$。因为有谁转向谁的区别，所以外积没有交换律。

$a\times b$的正负也可以理解为，把 $a$逆时针方向转到 $b$ 的方向，夹角为 $\theta$ 。当 $0\le \theta <\pi$时值为正；当 $\pi \le \theta <2\pi$时值为负。

如果 $a\Vert b$ ，那么由 $\sin 0^{\circ }=\sin 180^{\circ }=0,a\times b=0$，得到的数字结果也是 $0$ 。如果 $b$ 的终点在 $a$ 的左侧（假设已经共起点），那么 $a\times b>0$ ， $a$ 握向 $b$ 转过的角逆时针不超过 $180^{\circ }$ ，结果为正。如果 $b$ 的终点在 $a$的右侧，那么 $a\times b<0$， $a$ 握向 $b$转过的角逆时针超过了 $180^{\circ }$，或者说顺时针不超过 $180^{\circ }$ ，大拇指朝内，结果为负。

所以判断两点重合其实很简单：首先向量叉积必须等于$0$，这样能够保证两个向量共线，再加上点积为正的限制，保证夹角小于$90^{\circ }$，那么显然两点重合。

然后是判断点在凸包内。看着上面的图用右手转一转就知道了，顺时针枚举时，当一个点与线段两端点组成的两个向量叉积小于$0$的时候，点在凸包外。

代码

#include <bits/stdc++.h> #define MAX 505 #define eps 1e-9 using namespace std; struct vec{ double x, y; friend vec operator -(vec a, vec b){ //减法 return (vec){a.x-b.x, a.y-b.y}; } friend double operator ^(vec a, vec b){ //点积 return (a.x*b.x + a.y*b.y); } friend double operator *(vec a, vec b){ //叉积 return (a.x*b.y-a.y*b.x); } }a[MAX], b[MAX]; int m, n, ans = MAX*2; int g[MAX][MAX]; void floyd(){ for(int k = 1; k <= m; k++){ for(int i = 1; i <= m; i++){ for(int j = 1; j <= m; j++){ g[i][j] = min(g[i][k]+g[k][j], g[i][j]); } } } for(int i = 1; i <= m; i++){ //本题最小环较为特殊 ans = min(ans, g[i][i]); } } int main() { memset(g, 0x3f, sizeof(g)); cin >> m >> n; double t; for(int i = 1; i <= m; i++){ scanf("%lf%lf%lf", &a[i].x, &a[i].y, &t); } for(int i = 1; i <= n; i++){ scanf("%lf%lf%lf", &b[i].x, &b[i].y, &t); } for(int i = 1; i <= m; i++){ for(int j = 1; j <= m; j++){ int flag = 1; for(int k = 1; k <= n; k++){ double c = (a[i]-b[k])*(a[j]-b[k]); if(c < -eps){ //点在凸包外 flag = 0; break; } if(fabs(c)<eps && ((a[i]-b[k])^(a[j]-b[k])) > eps){ //叉积为0表示共线,点积为正表示夹角小于π/2,合起来表示i,j共点 flag = 0; break; } } if(flag) g[i][j] = 1; } } floyd(); if(ans == MAX*2){ puts("-1"); return 0; } cout << ans << endl; return 0; }