期望最大化

计算几何

Codeforces(2) dp(2) 图论(2) 思维(2) 搜索(8) 数据结构(3) 数论(5) 未归档(6) 洛谷(5) 课程实习(6)

/ 注册

全部文章 / 计算几何（共6篇）

判断点在三角形内部

利用叉积，如果点在三角形内部的话，则顺序处理全部边的话，这个点都在边的同一侧，直接用叉积判断 double det(double x1,double y1,double x2,double y2){ return x1*y2-x2*y1; } //x0,y0为需要的检查点，其他点顺时针顺序...

2019-07-18

0 473

The 13th Chinese Northeast Collegiate Programming Contest C. Line-line Intersection

比赛链接 http://https://codeforces.com/gym/102220 题目链接 https://codeforces.com/gym/102220/problem/C 题目大意：给n组二维坐标点，每一组两个点，组成一条直线。问有多少对直线存在公共点。解题思路 ...

2019-06-08

0 562

hdu5784 极角排序+two point

题意：给定平面内若干点，要求求出这些点组成的三角形中锐角三角形的个数。思路：锐角三角形，即这个三角形中不存在直角或者钝角。所以现在的思路是不断枚举三个点，看他们之间组成的角度在什么范围内，这样的复杂O（n*n*n），时限内肯定不能通过。对于二维平面的向量，用点积和叉积可以较为方便的判断他...

2019-05-16

0 979

极角排序理解

这里我们说的极角排序，指的是对于二维坐标中的点，当然也可以说是向量。极角排序的用途一般是预处理二维平面中的点，使之变得相对有序，接下来在有序的条件小用O（n）或者O（nlogn）处理，而不是无序条件下的O（n*n）的枚举。应用链接 https://www.cnblogs.com/gzr2018...

2019-05-15

0 1499

计算多边形的面积模板

//对多边形没有要求，但要求点按照顺时针或者逆时针的顺序1 for (int i = 0; i < x; i++) 2 scanf("%lf%lf", &a[i][0], &a[i][1]); 3 a[x][0] = a[0][0]; 4 a[x][...

2019-05-14

0 484

计算几何板子

点的定义 //考虑误差的加法 double add(double a, double b) { if (abs(a + b) < EPS*(abs(a) + abs(b)))return 0; return a + b; } struct P { double x, ...

2019-01-22

0 398