为什么不问问神奇海螺呢
为什么不问问神奇海螺呢
全部文章
几何之凸包问题
2018暑假组队赛记录(1)
ACM_心情(6)
codeforces2018(7)
DFS/BFS搜索(10)
Linux-Ubuntu(1)
python(1)
STL(12)
二分搜索(9)
健身(2)
几何之半平面交(6)
几何之旋转卡壳(2)
几何之模拟退火(5)
几何之面积问题(9)
几何技巧(7)
几何问题非模板问题(5)
动态规划之基础DP(54)
动态规划之状态压缩(1)
图论之二分图(5)
图论之强联通SCC(5)
图论之网络流(8)
套题(2)
学习(10)
学习资料(28)
年月问题(3)
思维(47)
括号匹配(2)
数学之博弈(6)
数据结构之Manacher(2)
数据结构之单调队列(1)
数据结构之字典树(3)
数据结构之字符串匹配KMP(4)
数据结构之并查集(10)
数据结构之生成树(3)
数据结构之线段树/树状数组(11)
数据结构之莫队算法(1)
数论之Mobius莫比乌斯反演(6)
数论之Nim博弈及变形(2)
数论之伯努利数(1)
数论之佩尔方程(4)
数论之因数相关(1)
数论之数学期望(2)
数论之组合数学(8)
数论之质数相关(1)
数论之进制转换(1)
暴力题(14)
未归档(37)
构造题(3)
模拟(9)
模板集合(打印)(9)
玄学黑科技(1)
生活分享(2)
电影(2)
算法学习(18)
自然溢出(1)
规律(7)
读书(7)
读书笔记(7)
贪心(21)
随机or玄学(1)
高精度(1)
归档
标签
去牛客网
登录
/
注册
Conchpeng
贵在坚持
全部文章
/ 几何之凸包问题
(共10篇)
凸包专题总结
1.安德鲁算法求 上+下凸包 2.Q.resize(k)和Q.reszie(k+1)的问题 3.几何题精度double和long long 避免混用,判断正负用sign 4.求凸包面积(无精度差),凸包周长 5.稳定凸包的理解:即不存在一个点,使得原先凸包上的点不再是新凸包上的点。即凸包上每...
2018-10-02
0
447
Bridge Across Islands POJ - 3608 [旋转卡壳求凸包最近距离]
Bridge Across Islands POJ - 3608 题意:求2个不相交凸多边形的最近距离 思路: 算法证明不会,只会用,只能描述过程 1.求出凸包P中y最小的序号idp, 凸包Q中y最大的序号idq 2.P和Q按着逆时针的顺序,枚举凸包P的所有边.当枚举边e时,找到距离该...
2018-08-14
0
621
Beauty Contest POJ - 2187 [求凸包直径,旋转卡壳]
Beauty Contest POJ - 2187 题意 : 求凸包上距离最远的两个点,普通做法O(n^2),旋转卡壳O(n); 关于旋转卡壳的总结 , 传送门 #include<cstdio> #include<vector> #include<...
2018-08-14
0
541
The Fortified Forest UVALive - 5211 [二进制枚举+凸包周长]
The Fortified Forest UVALive - 5211 题意:n棵树,每棵树对应有x,y,v,l分别代表横坐标,纵坐标,价值,砍这棵树能构成的篱笆长度。现在要求输出,在最小被砍价值的情况下,输出选了哪些树,还剩下多少长的篱笆。如果有多个相同的最小值,输出选点最少的。 思路: 二进...
2018-08-02
0
517
Wall POJ - 1113 [凸包周长]
Wall POJ - 1113 题意 : 求凸包周长 思路:处理出凸包,两点距离公式 #include<cstdio> #include<vector> #include<cmath> #include<string> #include<...
2018-07-30
0
495
Scrambled Polygon POJ - 2007 [凸包 / 极角排序]
Scrambled Polygon POJ - 2007 题意: 从(0,0)开始逆时针输出 凸包 思路 : 极角排序 / 凸包(跑完就是极角序)跑一遍 . 时间复杂度O(nlogn) 极角排序的两种写法 int cross(Vector A,Vector B){ ...
2018-07-30
0
859
Cows POJ - 3348 [凸包+面积]
Cows POJ - 3348 题意:求(int)凸包面积/50 关于求凸包面积的两种写法 第一种 ans.push_back(ans[0]); for(int i=0;i<(int)ans.size()-1;++i) res+=cross(ans[i],ans[i+1]); ...
2018-07-29
0
855
Polygons CodeForces - 166B [凸包,包含问题]
B. Polygons time limit per test 2 seconds memory limit per test 256 ...
2018-03-25
0
640
Cows POJ - 3348 [凸包+面积]
Cows Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 10169 Accepted: 4460 ...
2018-03-25
0
604
Wall POJ - 1113 [凸包]
Wall Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 39338 Accepted: 13432 ...
2018-03-25
0
528