Category Archives: 计算几何

UVA 10002 Center of Masses (凸包重心)

计算点集凸包的重心

 

CSU 1812 三角形和矩形 (计算几何)

计算给定三角形和矩形的交面积。 1. 直接暴力枚举三角形和矩形的线段,将交点存下来 2. 暴力枚举三角形每个点 …

Codeforces 678 F – Lena and Queries (分治,线段树,维护凸包)

n个询问,三种操作: 1. 在集合中加入点(x, y); 2. 在集合中删除操作i加入的点; 3. 在集合中询 …

计算几何一些板子

这次整理的模板主要是以点为对象,这样的写法显得更加灵活。 [crayon-5bc969003eda860244 …

HDU 5130 Signal Interference (圆与多边形交)

根据题目搞出圆方程,然后就是求圆和多边形交的面积。 [crayon-5bc969003f47e09502736 …

POJ 3608 Bridge Across Islands (旋转卡壳)

给出两个凸包,凸包可能是顺时针给出或者逆时针给出。求两个凸包的最小距离。 [crayon-5bc969003f …

POJ 2187 Beauty Contest (凸包,旋转卡壳)

给出n个散点,求距离最大的两点的距离. 先将搞出点集的凸包, 接着对凸包用旋转卡壳搞下即可. [crayon- …

旋转卡壳

最近准备搞搞几何,这次拿旋转卡壳开刀,来一发学习链接:666 1. 旋转卡壳计算凸包上两点距离最大值(凸包的直 …

Codeforces 630P Area of a Star (推公式)

计算n角星面积.

 

SGU 120 Archipelago (计算几何)

一个正n边形点根据顺时针编号,然后给出正n边形的两个点以及点的编号,求其它点的坐标。 先确定圆心,然后圆心到某 …