_奶酪
_奶酪
全部文章
计算几何
01分数规划例题(3)
01字典树(2)
ac自动机(1)
bfs/dfs(1)
C++学习记录(1)
clion(4)
GitHub的简单使用(2)
IDEA(1)
java(3)
JavaWeb(2)
kmp(2)
Linux(2)
mysql(2)
py大法好(3)
st表(1)
web前端(2)
主席树(1)
优先队列(3)
几何(1)
分割平面(1)
动态规划dp(13)
区间覆盖问题(1)
单调栈(2)
单调队列(1)
博弈(1)
卢卡斯定理(1)
后缀数组(8)
后缀自动机(3)
回文树(5)
回溯(1)
图(3)
图论(1)
堆(1)
套题总结(5)
字典树(3)
字符串hash(4)
字符串专题(2)
容斥原理(1)
差分(3)
并查集(4)
序列自动机(1)
思路是个好东西(29)
扩展kmp算法(2)
扩展欧几里得算法(1)
找规律题(6)
拓扑排序(1)
搜索(1)
数位dp(1)
数学期望/概率dp(4)
数学题(2)
数据结构学习笔记(2)
数论(8)
普通树(2)
最小生成树(4)
最短路径(2)
未归档(2)
权值线段树(3)
栈(1)
树状数组(9)
欧拉回路(1)
水题(4)
汇编学习笔记(1)
牛客网暑期多校题解(1)
矩阵快速幂(1)
离散化(1)
算法入门题目(66)
算法基础知识储备(16)
线性基(5)
线段树(4)
组合博弈(1)
组合数学(1)
编程语言的基础知识(1)
网页(1)
计数题(1)
贪心(2)
逆元(2)
递推(2)
链表(1)
马拉车算法(2)
高斯消元(1)
归档
标签
去牛客网
登录
/
注册
Step By Step
场场被暴打的菜鸡QAQ
全部文章
/ 计算几何
(共18篇)
【POJ2069&HDU3007】模拟退火算法之最小球/圆覆盖
启蒙博客:https://blog.csdn.net/AI_BigData_wh/article/details/77943787?locationNum=2&fps=1 POJ2069:最小球覆盖 被精度搞死。。POJ做题经常被精度卡到怀疑人生。。好感-1-1-1...-1 队友的...
2019-10-10
0
808
【2019CCPC秦皇岛:A】Angle Beats(离线+斜率Hash+分类讨论)
题目地址:https://codeforces.com/gym/102361/problem/A 题目: n个给定点,q个询问点,每次询问给出一个坐标A,问从n中选定两个点B,C,有多少种方案使得ABC是个直角三角形。 解题思路: 标称的思路是从极角考虑的,训练的时候我以为是从极角...
2019-10-05
0
416
【LA4992】Jungle Outpost(半平面交+二分)
解题思路: 紫书上的里例题。 关键是能把问题转化为求半平面,并且确定删除x点是连续删除的,且不确定具体删除的是哪x个点,所以需要判断每x个点组成的凸多边形的半平面交是否为空,这个半平面交就可以安放总部的区域。因为x的值不确定,可以0-n二分判定,注意二分的写法!输入的点是顺时针的,要转为逆时针!...
2019-09-25
0
467
【POJ3335】Rotating Scoreboard(多边形的内核-----半平面交+特殊情况)
题目地址:http://poj.org/problem?id=3335 题目: 顺时针(虽然题目没有特别讲明)给出多边形各边上的点,观众坐在多边形的边上,问是否能够在多边形内找到一点放置计分牌,使得在多边形边上坐着的所有观众都能看到这个计分牌。可以的话输出YES,否则NO 注意:Note t...
2019-09-24
0
641
【POJ3525】Most Distant Point from the Sea(半平面交+二分+直线平移)
题目地址:http://poj.org/problem?id=3525 题目: 给出一个形状为凸多边形的小岛,四周环海,求小岛内一点距海的最远距离,输出距离。 解题思路: 相当于在凸多边形内找一点,使得这个点到所有边的垂直距离的最小值最大。也即找到一个最大的圆,使得圆在凸多边形内和...
2019-09-21
0
366
【POJ3608】Bridge Across Islands(旋转卡壳求两凸多边形的最短间距)
题目地址:http://poj.org/problem?id=3608 解题思路: 注意:给出的点是按顺时针的,如果不是的话需要按照顺时针/逆时针排序 贴一下网上比较流行的原理解释: 1. 计算凸包P在y轴方向上的最小值记为yminP,和凸包Q在y轴方向上的最大值记为ymax...
2019-09-19
0
887
【LA4728】Square(求凸包(多边形)直径----旋转卡壳)
题目: pdf:https://icpcarchive.ecs.baylor.edu/external/47/4728.pdf 给出n个正方形的左下角坐标和边长,求这些正方形的最远点对的距离,输出距离平方和 解题思路: 凸包直径--旋转卡壳裸题。 注意旋转卡壳算法在计算时凸包的点...
2019-09-18
0
644
【UVA10256】The Great Divide(凸包相离判定)
提交地址: 题目: pdf:https://uva.onlinejudge.org/external/102/10256.pdf n个红点,m个蓝点,是否存在一条直线,使得任取一个红点和一个蓝点都在直线的异侧?这条直线不能穿过红点或者蓝点 解题思路: 先求出红点和蓝点的凸包,如果...
2019-09-17
0
444
【POJ2826】An Easy Problem?!(线段相交+分情况讨论+精度)
题目地址:http://poj.org/problem?id=2826 题目: 给出两条线段(木板的侧切面,木板宽度默认为1),求能接住雨水的水量,保留两位小数 解题思路: 这道题有很多种情况需要考虑。 (1)首先判断两条线段是否相交且只有一个交点。 (2)若满足条件(1)...
2019-09-11
0
483
【UVA11168】Airport(凸包+点到直线距离(一般式))
提交地址:https://vjudge.net/problem/UVA-11168 题目: pdf:https://uva.onlinejudge.org/external/111/11168.pdf 给出n个点,找到一条直线,使所有点在直线的同一侧,且到直线的距离之和的平均值最小 ...
2019-09-07
0
562
首页
上一页
1
2
下一页
末页