已注销

ACM模版篇

C++(4) CONTESTS(31) dfs && bfs(59) GitHub(1) Linux(4) OpenGL(2) PHP(5) Python(7) QT(3) Script(4) STL(24) 位运算(3) 其他(37) 动态规划(148) 区间(22) 图形打印(6) 图论(96) 字符串(39) 打表(13) 排序(31) 数学相关(153) 数据结构(73) 数论(101) 暴力解题(31) 机器学习(10) 栈(14) 树(51) 每周都有那么几天不想学习(2) 汇编(6) 知识点总结(17) 笔试试题(15) 网络流(7) 职场老油条(1) 计算几何(17) 贪心(62) 逐梦者(97) 郑州-大连(2) 问题残余(4) 骑行也是追梦(1)

/ 注册

全部文章 / ACM模版篇（共139篇）

Graham求凸包

ACM模版 Graham /* * Graham 求凸包 O(N * logN) * CALL: nr = graham(pnt, int n, res); res[]为凸包点集; */ struct point { double x, y; }; bool mult(point sp...

2021-05-22

0 441

判断线段相交

ACM模版判断线段相交 const double eps = 1e-10; struct point { double x, y; }; double min(double a, double b) { return a < b ? a : b; } double ...

2021-05-22

0 415

求多边形重心

ACM模版求多边形重心 /* * 求多边形重心 * INIT: pnt[]已按顺时针(或逆时针)排好序; | CALL: res = bcenter(pnt, n); */ struct point { double x, y; }; point bcenter(point pnt[...

2021-05-22

0 383

三角形相关重点

ACM模版三角形重点设三角形的三条边为a, b, c, 且不妨假设a <= b <= c. 面积三角形面积可以根据海伦公式求得： s = sqrt(p * (p - a) * (p - b) * (p - c)); p = (a + b + c) / 2; ...

2021-05-22

0 642

平面最近点对

ACM模版平面最近点对 /* * O(N * logN) */ const int N = 100005; const double MAX = 10e100, eps = 0.00001; struct Point { double x, y; int index; }; ...

2021-05-22

0 460

Liuctic计算几何库

ACM模版 Liuctic计算几何库 /* * Liuctic 的计算几何库 * p-Lpoint ln, l - Lline ls - Llineseglr - Lrad * 平面上两点之间的距离 p2pdis * (P1-P0)*(P2-P0)的叉积 xmulti * 确定两条线段是否相交 ...

2021-05-22

0 363

莫队算法

ACM模版莫队算法可以解决一类静态,离线区间查询问题。参考题目链接： BZOJ 2038 [2009国家集训队]小Z的袜子(hose) 题解：只需要统计区间内各个数出现次数的平方和。莫队算法,两种方法,一种是直接分成sqrt(n)块,分块排序。另外一种是求得曼哈顿距离...

2021-05-22

0 621

旋转卡壳

ACM模版求解平面最远点对参考题目链接： POJ 2187 Beauty Contest struct Point { int x, y; Point(int _x = 0, int _y = 0) { x = _x; y = _y...

2021-05-22

0 355

半平面交

ACM模版半平面交模版 const double eps = 1e-8; const double PI = acos(-1.0); int sgn(double x) { if (fabs(x) < eps) { return 0; } ...

2021-05-22

0 318

计算几何相关公式

ACM模版计算几何相关公式 Pick公式顶点坐标均是整点的简单多边形: 面积 = 内部格点数目 + 边上格点数目 / 2 - 1 S = n + s / 2 - 1 (其中n表示多边形内部的点数,s表示多边形边界上的点数,S表示多边形的面积) 已知圆锥表面积S求最大体积V...

2021-05-22

0 335