当前位置: 首页 > news >正文

计算几何

基本操作

判断两线段是否相交

跨立实验,两点是否在异侧,两条线段都成立即相交。

此实现不含端点

bool Cross(node A,node B,node C,node D){return ((B-A)*(C-A))*((B-A)*(D-A))<0&&((D-C)*(A-C))*((D-C)*(B-C))<0;
}

判断点是否在直线上

判外积是否为零可知是否共直线,需两点异侧,判内积是否为非正即可。

此实现含端点

bool inedge(node A,node B,node x){return (A-x)*(B-x)==0&&((A-x)^(B-x))<=0;
}

判断一点是否在多边形内部

射线法,从该点引一条水平射线,判断此线经过多边形的边次数奇偶性即可。
考虑边界问题,单独处理该点在多边形边上的情况。
经过多边形顶点的情况,只计算在其上方的边的个数。

bool inpolygon(node x){int tot=0;rpt(i,1,n)if(inedge(i==1?a[n]:a[i-1],a[i],x))return 1;rpt(i,1,n)tot+=Cross(i==1?a[n]:a[i-1],a[i],x,{inf,x.y});rpt(i,1,n)if(x.y-a[i].y==0&&a[i].x>x.x)tot+=((i==1?a[n].y:a[i-1].y)>x.y)+((i==n?a[1].y:a[i+1].y)>x.y);return tot%2;
}

例题

Security at Museums
简要题意
\(n\) 个顶点的平面多边形,集合为凸包的点集计数。

\(sol\)
先预处理出任意两点间线段是否在多边形内。
若中间经过端点则为合并两个线段,记忆化后可做到 \(O(n^3)\)
若中间经过多边形边(不含端点)则为假。
否则判中点是否在多边形内部即可。

然后考虑 \(dp\)
先钦定 \(dp\) 顺序,考虑一个凸包的极角一定是单调的,先按将线段按极角排序。
考虑极角相同的线段的顺序是一定的,将极角相同的线段一起转移。
一条线段中间经过的端点可选可不选,贡献为 \(2^n\)
一个凸包的贡献为所有线段贡献的乘积。
最后减去只有两个点的多余贡献即可。

http://www.hskmm.com/?act=detail&tid=27492

相关文章:

  • 2025开关按钮厂家最新推荐榜:开关按钮,带灯开关按钮,防水开关按钮,防爆开关按钮,防腐开关按钮等全种类覆盖,高品质设计与卓越性能口碑之选
  • 一种排查java.lang.OutOfMemoryError: Metaspace的方法
  • First Blog Post
  • 本站点即将在2025年改变研究方向和目标
  • 实用指南:12_OkHttp初体验
  • (AE)Adobe After Effects 2025 视频后期制作软件!安装包永久免费免激H解锁版下载与图文详细安装教程!!
  • Postgresql主从配置
  • 乒乓球
  • 2025年工程管理软件系统推荐榜:交付管理/工程协同/工程管理/智慧工地管理系统
  • 《程序员修炼之道》 阅读笔记一
  • 大型行为模型LBM超越语言模型的技术解析
  • 2025工程管理软件系统推荐榜:技术赋能下的场景化解决方案全景
  • 【LVS入门宝典】LVS-TUN模式原理与配备:跨越网络界限的负载均衡解决方案
  • Java基础-Eclipse工具-面向对象(1)
  • Avalonia UI 投资 Wilderness Labs
  • BLE开发新体验:四种模式全解析,源码免费开放
  • JBoltAI V4 - 那年-冬季
  • 【EI检索】2025年智能决策与机器学习国际学术会议 (ICIDML 2025)
  • 10月9号
  • Qwen3技术报告
  • 赋能智慧监管:国标GB28181平台EasyGBS在明厨亮灶场景中的深度应用
  • CFD与FDM, FEM, FVM的关系?
  • 央国企高管团队为何频繁流失?揭示薪酬结构失衡的深层原因与优化策略
  • 在Ubuntu 22.04系统上安装libimobiledevice的步骤
  • Redis sentinal模式,master挂了的 选举过程
  • 软件技术基础第一次
  • 音频基础知识
  • 有限体积法和有限差分法、有限元法的区别。
  • 用户行为素材可视化
  • “十五五”战略下,央国企人事系统如何破局增效?T集团数字化转型案例分享