永远鲜红的幼月

分类

CF(19) dp(6) gcd的应用(1) sort(4) spfa(1) 二分(12) 几何(1) 博弈(2) 固定算法(1) 图论(11) 套题(5) 字符串匹配(1) 并查集(4) 思维(2) 搜索(4) 数学题(2) 数据结构(10) 数论(4) 未归档(192) 树状数组(1) 状压DP(1) 科普(3) 线段树(2) 网络流(3) 计算几何(4) 计算几何学习(17) 贪心(1) 题解(1)

/ 注册

全部文章（共315篇）

半平面交题目汇总

在此处总结关于半平面交的题目（基本都是POJ的）：目录 POJ-1279-Art Gallery（测板子） POJ-1474-Video Surveillance（测半平面相交板子） POJ-1755-（NO AC） POJ-2104-（NO AC） POJ-2187-（NO AC） ...

2019-02-25

0 582

计算几何基础--半平面求交

半平面，平面的一半。半平面求交，就是求得n个半平面的相交的平面。一开始可能不太好理解。举个例子：一条线，有两个半平面两条线，四个半平面，有一个相三条线，7个半平面，然后有一个相交的区域，这个区域就是半平面 ...

2019-02-24

0 670

计算几何基础--线段的性质

线段的计算。也是计算几何的基础之一。判断两线段相交，求交点，等都是必不可少的内容。常用的解析几何方法使用三角函数和除法，使得计算的代价较高&&容易产生较大的误差。如计算两条近似平行的直线y=kx+b，的交点，涉及到了除法运算。那么对计算机的精确度要求就非常高了。因此如果能够在计...

2019-02-21

0 705

计算几何基础--判断点的位置

点的定位点的定位属于几何查找，是计算几何中的一个重要的问题。其包括点在三角形内外，多边形内外判断，平面剖分中的位置等。关于出现在这篇文章中但没有给出的自定义函数，如：CroMul(V a,V b)等，上篇博客有提到，向量叉乘。判断点是否在线上：我们可以用刚刚我们提到的叉积重要性质，即...

2019-02-20

0 783

计算几何基础--规范数据表示

计算几何中的数据表示：为了规范代码的格式，整理一下数据的表示格式：本文中都用a（x1，y1），b（x2，y2）和c表示向量。向量加减法：设二维向量a(x1,y1),向量b(x2,y2).向量c。向量的加法：c=a+b=（x1+x2，y1+y2）; 因为向量是矢量，带有方向，因此...

2019-02-20

0 460

2019 CCCC-GPLT 练习赛(三)

7-1 计算物体下落的距离思路：演草纸计算，输出。 int main(){ printf("height = 45.00\n"); } 7-2 含有8的数字的个数思路：暴力 int main(){ int a,b;scanf("%d%d&qu...

2019-02-20

0 666

Manacher（马拉车）算法-最长回文子串O(n)

存一个板子最长回文子串的线性处理方法，注意是子串，和子序列不同写一个板子：照着手跑一遍在参考一下别人的博客就很清楚了。 code： string Manacher(string s){ // Insert '#' string t="$#"; for(int ...

2019-02-20

0 467

POJ-2983-Is the Information Reliable?（线性约束，最长路，判断正环）

题目链接：http://poj.org/problem?id=2983 题目大意：给出n个点，m个关系，每个关系说明P a b val，a在b的北边val远，V a b，a在b的北边至少1单位远。问这些关系是否能推出一个不矛盾的大关系。思路：确定距离的双向路，建立两个边，即:f[a]-f[...

2019-02-17

0 574

HDU-3666-THE MATRIX PROBLEM（差分约束系统）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3666 题目大意：一个n*m的矩阵和两个数L，U，对于矩阵中的每个元素，存在两个数组an，bn，使得L<=arr[i][j]*a[i]/b[j]<=U；如果存在这样两个数组，输出YES，否则...

2019-02-17

0 581

POJ-1364，UVA-515-King （区间约束）

题目链接：http://poj.org/problem?id=1364 题目链接：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=...

2019-02-13

0 552