搜索结果
查询Tags标签： 凸包，共有 12条记录-
题解[CF575E]Spectator_Riots
题意 一个球场，可以看作 \(10^5\times10^5\) 的矩形，每个位置都是一个整点。一个位置 \((x,y)\) 位于球场内当且仅当 \(x\in[0,10^5]\and y\in[0,10^5]\) 。 有 \(n\) 个可能捣乱的黑粉，第 \(i\) 个在位置 \((x_i,y_i)\) 上，速度为 \(v_i\)，即一秒内可能跑到任意一个…
2022/7/31 23:42:41 人评论 次浏览 -
凸包和网络流模板
凸包模板 这题是整数范围，需要时请改浮点数 #include<bits/stdc++.h> #define int long long using namespace std; const int maxn=5110; int n; struct node{int x,y; }s[maxn],e[maxn]; int top; inline int area(node a1,node a2,node b1,node b2){return (a2.…
2022/7/9 23:22:17 人评论 次浏览 -
计算几何-闵可夫斯基和
计算几何-闵可夫斯基和 闵可夫斯基和 闵可夫斯基和，又称作闵可夫斯基加法，是两个欧几里得空间的点集的和，以德国数学家闵可夫斯基命名。（小知识：闵可夫斯基曾经做过爱因斯坦的老师。） 闵可夫斯基和是两个欧几里得空间的点集的和，也称为这两个空间的膨胀集，被定义为…
2022/6/3 23:20:10 人评论 次浏览 -
587. 安装栅栏(凸包问题)
587. 安装栅栏在一个二维的花园中，有一些用 (x, y) 坐标表示的树。由于安装费用十分昂贵，你的任务是先用最短的绳子围起所有的树。只有当所有的树都被绳子包围时，花园才能围好栅栏。你需要找到正好位于栅栏边界上的树的坐标。示例 1: 输入: [[1,1],[2,2],[2,0],[2,4],[…
2022/4/27 6:12:59 人评论 次浏览 -
[算法笔记]凸包问题
二维凸包问题 Andrew算法 写在前面：本文参考自：刘汝佳《算法竞赛入门经典-训练之南》介绍： 凸包：把给定点包围在内部的、面积最小的凸多边形。 Andrew算法是Graham算法的变种，速度更快，数值稳定性也更好。 算法实现：首先把全部点按照x从小到打排序（x相等，则按照y…
2022/3/6 20:15:22 人评论 次浏览 -
算法笔记（二）凸包问题convex hull
1、问题定义： （1）输入：平面上的n个点的集合Q ；输出： CH(Q)，即Q的凸包 （2）Q的凸包：是一个最小凸多边形 P，Q的点在P上或者在P内 （3）凸多边形P： 连接P内任意两点的边都在P内 2、基本思想： （1）当沿着凸包逆时针漫游时，总是向左转； （2）在极坐标系下按照极…
2021/10/26 17:12:03 人评论 次浏览 -
算法笔记（二）凸包问题convex hull
1、问题定义： （1）输入：平面上的n个点的集合Q ；输出： CH(Q)，即Q的凸包 （2）Q的凸包：是一个最小凸多边形 P，Q的点在P上或者在P内 （3）凸多边形P： 连接P内任意两点的边都在P内 2、基本思想： （1）当沿着凸包逆时针漫游时，总是向左转； （2）在极坐标系下按照极…
2021/10/26 17:12:03 人评论 次浏览 -
凸包与直线的关系
给一个逆时针的凸包和一条线,问你线的左边的和凸包的交面积 https://onlinejudge.u-aizu.ac.jp/courses/library/4/CGL/4/CGL_4_C int n; Point p[N],ch[N]; Point last[N]; //最后存在的点 //两直线交点 Point Cross_point(Point a,Point b,Point c,Point d) { //Line1:…
2021/9/14 6:05:03 人评论 次浏览 -
凸包与直线的关系
给一个逆时针的凸包和一条线,问你线的左边的和凸包的交面积 https://onlinejudge.u-aizu.ac.jp/courses/library/4/CGL/4/CGL_4_C int n; Point p[N],ch[N]; Point last[N]; //最后存在的点 //两直线交点 Point Cross_point(Point a,Point b,Point c,Point d) { //Line1:…
2021/9/14 6:05:03 人评论 次浏览 -
康复训练+To Do List
模板： 字符串:[ ] Sa+O(1)height [ ] Sam+线段树合并 [ ] 广义Sam [ ] kmp [ ] ac自动机 [ ] Pam [ ] Manacher筛法[ ] 莫比乌斯反演 [ ] 线筛筛一般函数 [ ] 狄利克雷卷积及某些函数的性质 [ ] 杜教筛 [ ] min_25筛多项式[ ] fft,ntt,mtt [ ] 多项式全家桶（下降幂，插值…
2021/7/27 23:35:54 人评论 次浏览 -
康复训练+To Do List
模板： 字符串:[ ] Sa+O(1)height [ ] Sam+线段树合并 [ ] 广义Sam [ ] kmp [ ] ac自动机 [ ] Pam [ ] Manacher筛法[ ] 莫比乌斯反演 [ ] 线筛筛一般函数 [ ] 狄利克雷卷积及某些函数的性质 [ ] 杜教筛 [ ] min_25筛多项式[ ] fft,ntt,mtt [ ] 多项式全家桶（下降幂，插值…
2021/7/27 23:35:54 人评论 次浏览 -
4.典型的分治算法: 选最大与最小, 选第二大, 选择问题, 卷积, 快速傅立叶变换, 平面点集的凸包
本文内容为北大慕课课程的算法分析与设计的课程讲义, 将其整理为OneNote笔记同时添加了本人上课时的课堂笔记, 且主页中的思维导图就是根据课件内容整理而来, 为了方便大家和自己查看，特将此上传到CSDN博文中, 源文件已经上传到我的资源中,有需要的可以去看看, 我主页中的…
2021/5/6 12:25:38 人评论 次浏览
