夏晓光(loveJY)的博客

啊啊啊唐爷爷强

这个和之前那个很相近啊,就是钟神出的b题

首先把一个三元的是没用的,知道前两个就知道第三个了

拿前两个元素作为坐标,每个点拍到平面上

我们就会发现,这个操作类似于一个加权平均数,也就是类似于表示出一些向量围成的面积

三个点就是三角形内的点都能表示

n个点就是凸包内的点都能表示

现在我们想选出最少的边使得所有目标点被圈在中间

首先你会发现这些边一定是包括了所有目标点凸包

也就是所有点都在这个边的一侧

用叉积,叉积大于0在左侧,$x1y2-x2y1$

然后我们就能$O(m^2*n)$找到所有合法边了

找到以后呢?按照传统OI点到为止的规则,这个题已经切了

但是他不讲武德,还是要求一个最小环

最小环我防出去了,防出去了啊

然后它来了个点在线段/直线上

我反手一个点积大于0判掉所有在直线上的

然后此时他竟然来一个点就能成为答案的

我大意了啊,没有闪

于是90好几发

code:

//考虑怎么做?
//凸包
//一条边在另外所有点的一侧就加入
//然后找最小环
//叉积判断?
//del x * del y
#include<bits/stdc++.h>
#define db double
using namespace std;
const db eps = 1e-8;
const int MAXN = 507;
struct  ND {
	db x, y, z;
} e[MAXN], d[MAXN];
//xy-xy
inline db cross(ND xx, ND yy, ND zz) {
	return (xx.x - zz.x) * (yy.y - zz.y) - (xx.y - zz.y) * (yy.x - zz.x);
}
//xx+yy
inline db dot(ND xx, ND yy, ND zz) {
	return (xx.x - zz.x) * (yy.x - zz.x) + (xx.y - zz.y) * (yy.y - zz.y);
}

int n, m;
int g[MAXN][MAXN];

int main() {
	scanf("%d%d", &m, &n);
	for(int i = 1; i <= m; ++i)scanf("%lf%lf%lf", &e[i].x, &e[i].y, &e[i].z);
	for(int i = 1; i <= n; ++i)scanf("%lf%lf%lf", &d[i].x, &d[i].y, &d[i].z);
	memset(g, 0x3f3f3f3f, sizeof(g));
	for(int i = 1; i <= m; ++i) {
		int flg = 1;
		for(int j = 1; j <= n; ++j) {
			if(fabs(e[i].x - d[j].x) > eps || fabs(e[i].y - d[j].y) > eps) {
				flg = 0;
				break;
			}
		}
		if(flg) {
			puts("1");
			return 0;
		}
	}
	for(int i = 1; i <= m; ++i) {
		for(int j = 1; j <= m; ++j) {
			if(i != j) {//看看这线段是否牛逼
				int flg = 1;
				for(int k = 1; k <= n; ++k) {
					if(fabs(cross(e[i], e[j], d[k])) < eps && dot(e[i], e[j], d[k]) > eps) {
						//共线不在线段
						flg = -1;
						break;
					}
					if(cross(e[i], e[j], d[k]) > eps) {
						flg = -1;
						break;
					}
				}
				if(flg == -1)continue;
				g[i][j] = 1;
			}
		}
	}
	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][j], g[i][k] + g[k][j]);
			}
		}
	}
	int ans = 1e9;
	for(int i = 1; i <= m; ++i)ans = min(ans, g[i][i]);
	if(ans == 1e9)puts("-1");
	else printf("%d\n", ans);
	return 0;
}