const double eps = 1e-8;
const double inf = 1e30;
int sign(double d){
return d < -eps ? -1 : (d > eps);
}
struct point{
double x, y;
point(double _x=0, double _y=0) : x(_x), y(_y) {}
void read(){
scanf("%lf%lf", &x, &y);
}
};
//直线p1-p2和直线a*x+b*y+c=0的交点
point intersect(point p1, point p2, double a, double b, double c){
double u = fabs(a * p1.x + b * p1.y + c);
double v = fabs(a * p2.x + b * p2.y + c);
return point((p1.x * v + p2.x * u) / (u + v), (p1.y * v + p2.y * u) / (u + v));
}
//求经过st和ed(保证这两个点不相等)的直线a*x+b*y+c=0的三个参数
void tran(point st, point ed, double& a, double& b, double& c){
a = st.y - ed.y;
b = ed.x - st.x;
c = (ed.y - st.y) * st.x - (ed.x - st.x) * st.y;
}
//多边形类
struct poly{
static const int N = 1005; //点数的最大值
point ps[N+5]; //逆时针存储多边形的点,[0,pn-1]存储点
int pn; //点数
poly() { pn = 0; }
//加进一个点
void push(point tp){
ps[pn++] = tp;
}
//第k个位置
int trim(int k){
return (k+pn)%pn;
}
void clear(){ pn = 0; }
};
//求该凸多边形org(确保org的点是逆时针方向的)在半平面a*x+b*y+c < 0 的部分
poly incise(poly org, double a, double b, double c){
poly ans;
point* ps = org.ps;
int i;
for(i = 0; i < org.pn; i++){
if(sign(a*ps[i].x+b*ps[i].y+c) < 1){
ans.push(ps[i]);
}else{
int g = org.trim(i-1);
if(sign(a*ps[g].x+b*ps[g].y+c) < 0){
ans.push(intersect(ps[g], ps[i], a, b, c));
}
g = org.trim(i+1);
if(sign(a*ps[g].x+b*ps[g].y+c) < 0){
ans.push(intersect(ps[g], ps[i], a, b, c));
}
}
}
return ans;
}
//求该凸多边形org(确保org的点是逆时针方向的)在st-->ed的左边(即从st看向ed时的左手边)的部分
poly incise(poly org, point st, point ed){
double a, b, c;
point tp;
tran(st, ed, a, b, c);
//tp是st-->ed的左边的半平面的一个代表点
tp.x = st.x - (ed.y - st.y);
tp.y = st.y + (ed.x - st.x);
if(sign(a*tp.x+b*tp.y+c) < 0){
return incise(org, a, b, c);
}else{
return incise(org, -a, -b, -c);
}
}
分享到:
相关推荐
计算几何学习笔记
这里面包含了好多计算几何的函数,像半平面交,判定一个点是否在多变形内,以及一些常用的函数。
李澎煦半平面交的算法及其应用 朱泽园半平面交的新算法及其实用价值
计算几何半平面交,poj2451 一题是模版题,这里的代码可以作为模版使用,速度比较快
包含点、线、多边形、凸多边形、圆、半平面交等算法的板子
kuangbin的ACM模板动态规划计算几何:线与线求交,线与面求交,求凸包,半平面求交等若干图论问题:最小生成树 最短路 强连通分量、桥和割点 等
7.11 计算几何:线与线求交,线与面求交,求凸包,半平面求交等 7.15 若干图论问题:最小生成树 最短路 强连通分量、桥和割点 等 7.16 网络流算法:基本的网络流算法,Dinic算法,带上下界的网络流,最小费用流 ...
北京大学2011年暑期acm培训课件 ...6) 计算几何:线与线求交,线与面求交,求凸包,半平面求交等 7) 网络流算法:基本的网络流算法,Dinic算法,带上下界的网络流,最小费用流 8) 数学题:组合数学,数论等
1.平面扫描2 2.凸包3 3.旋转卡壳5 4.半平面交7 5.闵可夫斯基和 10 6.平面区域10 7.平面最近点对 12 1.平面扫描 2.凸包
一些计算机ACM题目源码 ,包括凸包, 半平面交,一些基础算法。
后缀数组 动态规划 组合游戏 Pólya计数法 计算几何 最小割模型在信息学竞赛中的应用 半平面交的新算法 线段树 伸展树 高斯消元 ...
后缀数组 动态规划 组合游戏 Pólya计数法 计算几何 最小割模型在信息学竞赛中的应用 半平面交的新算法 线段树 伸展树 高斯消元 ...
+ [半平面交](#半平面交) * [矩阵](#矩阵) + [矩阵](#矩阵-1) + [高斯消元](#高斯消元) * [数学方法](#数学方法) + [数学思想](#数学思想) + [数学归纳法](#数学归纳法) + [多项式](#多项式) + [数形结合]...
半平面交 圆的反演 三角剖分 Voronoi图 立体计算几何 数据结构 动态点分治 动态图 K-D Tree 线段树复杂度分析(类似于jry线段树) 莫队二次离线 仙人掌 带花树 支配树 ETT (?) TopTree (??) ...
计算几何(平面解几及其应用,向量,点积及其应用,叉积及其应用,半平面相交,求点集的凸包,最近点对问题,凸多边形的交,离散化与扫描) 数据结构(广度优先搜索,验证括号匹配,表达式计算,递归的编译,Hash...
半平面交 计算几何库 数据结构 闭散列法整数hash 开散列法整数hash 字符串hash 堆 二维树状数组 Trie树 二叉查找树 线段树 RMQ LCA+RMQ SB-Tree 数论 生成紧凑素数表 分解质因子 最大公约数 a^b ...
9.半平面交 图论: 基础:前向星 1.最短路(优先队列dijkstra) 2.判断环(tarjan算法) 3.最小生成树(Kruskal 模板) 4.最小生成树(Prim) 5.Dicnic最大流(最小割) 6.无向图最小环(floyd) 7.floyd算法的动态规划(通过部分...
9.4.1半平面的交 9.4.2增量构造方法 9.4.3分治算法 9.4.4减量算法 9.4.5平面扫描算法 思考题 第10章缓冲区分析算法 10.1概述 10.2缓冲区边界生成算法基础 10.3点缓冲区边界生成算法 10.4线缓冲区边界...
目录序前言第1章算法设计和分析1.1概述1.2算法设计原则1.3算法复杂性...计算几何基础2.1维数扩展的9交集模型2.1.1概述2.1.2模型介绍2.1.3空间关系的判定2.2矢量的概念2.2.1矢量加减法2.2.2矢量叉积2.3...
腐植煤的宏观煤岩类型分为四种,即:光亮型煤、半光亮型煤、半暗淡型煤和暗淡型煤。 15煤的化学组成及随煤变质程度加深的变化规律? 答煤的化学组成:相当复杂,大致分为有机质和无机质两大类。其中有机质为主体,也...