[转载]https://blog.****.net/linxilinxilinxi/article/details/81810944 先码为敬，慢慢学习！！

1 前言

1.1 计算几何算法

ACM各种算法中计算几何算是比较实际的算法，在很多领域有着重要的用途

常用算法包括经典的凸包求解，离散化及扫描线算法、旋转卡壳、半平面交等

1.2 计算几何题目特点及要领

• 大部分不会很难，少部分题目思路很巧妙

• 做计算几何题目，模板很重要，模板必须高度可靠

• 要注意代码的组织，因为计算几何的题目很容易上两百行代码，里面大部分是模板。如果代码一片混乱，那么会严重影响做题正确率。

• 注意精度控制

• 能用整数的地方尽量用整数，要想到扩大数据的方法（扩大一倍，或扩大sqrt2）。因为整数不用考虑浮点误差，而且运算比浮点快

1.3 预备知识

见ACM几何基础篇

https://linxi99.gitee.io/20190211/ACM几何基础篇/

https://blog.****.net/linxilinxilinxi/article/details/81750327

计算几何将用到大量基础篇中的函数与知识

2 凸包

2.1 定义

2.1.1 凸多边形

过多边形的任意一边做一条直线，如果其他各个顶点都在这条直线的同侧，则把这个多边形叫做凸多边形

凸包求解算法的基础便是凸多边形的定义与性质

2.1.2 凸包

假设平面上n个点，过某些点作一个多边形，使这个多边形能把所有点都“包”起来。当这个多边形是凸多边形的时候，我们就叫它“凸包”

形象理解：皮筋包裹钉子群

2.2 颜料配色问题

2.2.1 问题描述

假设每种颜料都拥有$(R,G,B)(R,G,B) (R,G,B)$(R,G,B)(R,G,B)(R,G,B)