Tag-计算几何

Icontofig 's Blog // 我们的征程是星辰大海!Away From OI,Come to ICPC(查看友链请点About Me)

 2019-08-04 16:38:46 |  0 Comments  |  计算几何 凸包

SPOJ SPOINTS - Separate Points 凸包+判断点与凸包、线段的位置

题目大意

平面直角坐标系上有n个黑点和m个白点,判断能否用一条直线将黑点和白点分成互不相交的两部分。

题解

这题一眼望去就是个裸凸包+判断是否在凸包内。

但是我们要多考虑一些事情,就做一下分类讨论。

如果没有黑点或者没有白点,那么肯定是可以分开的。

如果黑点和白点都只有一个,那么判断一下黑点和白点是否重合。

如果其中一个有两个,另一种有1个,那么我们要判断后者的点是否在前者两个点所在的线段上。

具体的话,就是如下这样子:

if(cnt1 == 1 && cnt2 == 2){
    if(cross(st[1]-sp[1],st[1] - sp[2]) == 0 && mul(sp[1] - st[1],sp[1] - sp[2]) >= 0)
        flag = false;
}
else if(cnt1 == 2 && cnt2 == 1){
    if(cross(sp[1] - st[1],sp[1] - st[2]) == 0 && mul(st[1] - sp[1],st[1] - st[2]) >= 0)
        flag = false;
}

然后如果这两个集合都是组成一条线段的话,则判断两条线段是否相交(使用叉积)

如果以上情况都不满足,那么我们就直接求出两个凸包,然后分别判断两个集合的点是否在另一个集合所有点的凸包中,如果在,就输出NO,否则输出YES。

最终复杂度是O(n+nlogn)。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 505;
typedef long long ll;
struct point{
    int x,y;
}p[maxn],q[maxn],st[maxn],sp[maxn];
int cross(point a,point b){
    return a.x * b.y - b.x * a.y;
}
point operator - (point a,point b){
    point t;
    t.x = a.x - b.x;
    t.y = a.y - b.y;
    return t;
}
bool operator == (point a,point b){
    return (a.x == b.x &&
 2019-06-06 17:27:01 |  0 Comments  |  三分 计算几何

Codeforces Gym 101981 D Country Meow 三维计算几何

题目大意

给出n个点的三维空间坐标,在空间内找任意一个点使得其距离这n个点中的最远的点的欧几里得距离最小。

题解

说实话,马上考期末了应该复习来着,但是总是感觉不写完这篇心里闷得慌……

这题实际上应该是个最小覆盖球,不过此篇博客不打算使用这种算法来做,这里介绍一种比较纯数学的方法去做。

我们假设我们选的点为P(x,y,z),

那么距离的平方的表达式一定为

如果固定其中的x,y,那么这个式子就是关于z的一个二次函数,且是有极小值的二次函数。

对于x,y当然也是同理的。

我们要求的就是所有距离的平方的最大值的最小值,于是就是求取极小值的一个过程。

众所周知二次函数是个单峰函数,最小值就是极小值,而单峰函数求极小值我们可以用三分来做。

但是这有三个变量(x,y,z)那怎么办?

上面说到如果其中两个固定了,那么不会对第三个变量取值后的函数值产生影响。

于是我们考虑可以使用三分套三分套三分(三层三分套在一起),由于每一层三分并不会影响另外两层三分,于是这个做法是正确的。

这个题没有卡精度,其实eps没有什么用处。

代码

#include <bits/stdc++.h>
using namespace std;
struct point{
	double x,y,z;
}p[105];
int n;
double eps = 1e-6;
double mix,miy,miz,mxx,mxy,mxz;
double calc3(double x,double y,double z){
	double ans = 0;
	for(int i = 1;i <= n;++i){
		double ret = 0;
		ret += (x - p[i].x) * (x-p[i].x);
		ret += (y - p[i].y) * (y-p[i].y);
		ret += (z - p[i].z) * (z-p[i].z);
		ans = max(ans,ret);
	}
	return ans;
}
double calc2(double x,double y){
	double l = miz  - eps,r = mxz + eps,midl,midr;
	double ans = 1e15;
	for(int cnt2 = 1;cnt2 <= 60;++cnt2){
		midl = l + (r-l)/3
Title - Artist
0:00