凸包
题：
bzoj3203 bzoj1185 bzoj1069 bzoj2300 bzoj2961
解一：分治法
时间复杂度：O(n㏒n)。 思路：应用分治法思想，把一个大问题分成几个结构相同的子问题，把子问题再分成几个更小的子问题……。然后我们就能用递归的方法，分别求这些子问题的解。最后把每个子问题的解“组装”成原来大问题的解。 步骤： 1.把所有的点都放在二维坐标系里面。那么横坐标最小和最大的两个点 P1 和 Pn 一定是凸包上的点（为什么呢？用反证法很容易证明，这里不详讲）。直线 P1Pn 把点集分成了两部分，即 X 轴上面和下面两部分，分别叫做上包和下包。 2.对上包：求距离直线 P1Pn 最远的点，即下图中的点 Pmax 。 3.作直线 P1Pmax 、PnPmax，把直线 P1Pmax 左侧的点当成是上包，把直线 PnPmax 右侧的点也当成是上包。 4.重复步骤 2、3。 5.对下包也作类似操作。
然而怎么求距离某直线最远的点呢？我们还是用到解一中的公式： 设有一个点 P3 和直线 P1P2 。（坐标：p1(x1,y1)，p2(x2,y2)，p3(x3,y3)） 对上式的结果取绝对值，绝对值越大，则距离直线越远。
注意：在步骤一，如果横坐标最小的点不止一个，那么这几个点都是凸包上的点，此时上包和下包的划分就有点不同了，需要注意。
解二：Jarvis步进法
时间复杂度：O(nH)。（其中 n 是点的总个数，H 是凸包上的点的个数） 思路：
纵坐标最小的那个点一定是凸包上的点，例如图上的 P0。 从 P0 开始，按逆时针的方向，逐个找凸包上的点，每前进一步找到一个点，所以叫作步进法。 怎么找下一个点呢？利用夹角。假设现在已经找到 {P0，P1，P2} 了，要找下一个点：剩下的点分别和 P2 组成向量，设这个向量与向量P1P2的夹角为 β 。当 β 最小时就是所要求的下一个点了，此处为 P3 。
注意：
找第二个点 P1 时，因为已经找到的只有 P0 一个点，所以向量只能和水平线作夹角 α，当 α 最小时求得第二个点。 共线情况：如果直线 P2P3 上还有一个点 P4，即三个点共线，此时由向量P2P3 和向量P2P4 产生的两个 β 是相同的。我们应该把 P3、P4 都当做凸包上的点，并且把距离 P2 最远的那个点（即图中的P4）作为最后搜索到的点，继续找它的下一个连接点。
解三：Graham扫描法
时间复杂度：O(n㏒n) 思路：Graham扫描的思想和Jarris步进法类似，也是先找到凸包上的一个点，然后从那个点开始按逆时针方向逐个找凸包上的点，但它不是利用夹角。 步骤：
1.把所有点放在二维坐标系中，则纵坐标最小的点一定是凸包上的点，如图中的P0。 2.把所有点的坐标平移一下，使 P0 作为原点，如上图。 3.计算各个点相对于 P0 的幅角 α ，按从小到大的顺序对各个点排序。当 α 相同时，距离 P0 比较近的排在前面。例如上图得到的结果为 P1，P2，P3，P4，P5，P6，P7，P8。我们由几何知识可以知道，结果中第一个点 P1 和最后一个点 P8 一定是凸包上的点。 （以上是准备步骤，以下开始求凸包） 以上，我们已经知道了凸包上的第一个点 P0 和第二个点 P1，我们把它们放在栈里面。现在从步骤3求得的那个结果里，把 P1 后面的那个点拿出来做当前点，即 P2 。接下来开始找第三个点： 4.连接P0和栈顶的那个点，得到直线 L 。看当前点是在直线 L 的右边还是左边。如果在直线的右边就执行步骤5；如果在直线上，或者在直线的左边就执行步骤6。 5.如果在右边，则栈顶的那个元素不是凸包上的点，把栈顶元素出栈。执行步骤4。 6.当前点是凸包上的点，把它压入栈，执行步骤7。 7.检查当前的点 P2 是不是步骤3那个结果的最后一个元素。是最后一个元素的话就结束。如果不是的话就把 P2 后面那个点做当前点，返回步骤4。 最后，栈中的元素就是凸包上的点了。 以下为用Graham扫描法动态求解的过程：
解四：Melkman算法
说真的，这个算法我也还没有看清。网上的资料也少的可怜，我暂且把网上的解释截个图在这里，往后搞懂以后再回来补上。 或者有人看懂了的，希望不吝指教，不甚感激！
扩展：
以上讨论的只是二维的凸包，如果延生为三维、多维的凸包问题呢？如何求解？ 不过首先，二维凸包可以用来解决围栏问题、城市规划问题、聚类分析等等。但是三维、多维的凸包可能的使用范畴有哪些？ (凸包的原文链接：http://blog.csdn.net/bone_ace/article/details/46239187)
模板
//poj2187 Graham AC_code
using namespace std;
int read()
{
int x=
0,f=
1;char ch=getchar();
while(ch<
'0'||ch>
'9'){
if(ch==
'-')f=-
1;ch=getchar();}
while(ch>=
'0'&&ch<=
'9'){
x=
x*10+ch-
'0';ch=getchar();}
return x*f;
}
int n,top;
double ans;
double
sqr(double x)
{
return x*x;
}
struct P{
double
x,
y;
P(){}
P(double _x,double _y):
x(_x),
y(_y){}
friend P operator +(P a,P b){
return P(a.
x+b.
x,a.
y+b.
y);
}
friend P operator -(P a,P b){
return P(a.
x-b.
x,a.
y-b.
y);
}
friend double operator
*(P a,P b){
return a.
x*b.
y-a.
y*b.
x;
}
friend double operator/(P a,P b){
return a.
x*b.
x+a.
y*b.
y;
}
friend bool operator==(P a,P b){
return fabs(a.
x-b.
x)<eps&&fabs(a.
y-b.
y)<eps;
}
friend bool operator!=(P a,P b){
return !(a==b);
}
friend bool operator<(P a,P b){
if(fabs(a.
y-b.
y)<eps)
return a.
x<b.
x;
return a.
y<b.
y;
}
friend double dis2(P a){
return sqr(a.x)+
sqr(a.y);
}
friend void
print(P a){
printf(
"%.2lf %.2lf\n",a.
x,a.
y);
}
}p[
50005],
q[50005];
bool cmp(P a,P b)
{
if(fabs((b-p[
1])
*(a-p[
1]))<eps)
return dis2(a-p[
1])<dis2(b-p[
1]);
return (a-p[
1])
*(b-p[
1])>
0;
}
void graham()
{
for(
int i=
1;i<=n;i++)
if(p[i]<p[
1])swap(p[i],p[
1]);
sort(p+
2,p+n+
1,cmp);
q[++top]=p[
1];
q[++top]=p[
2];
for(
int i=
3;i<=n;i++)
{
while((
q[top]-
q[top-1])
*(p[i]-
q[top-1])<eps&&top>
1)top--;
q[++top]=p[i];
}
}
void RC()
{
q[top+1]=
q[1];
int now=
2;
for(
int i=
1;i<=top;i++)
{
while((
q[i+1]-
q[i])
*(q[now]-
q[i])<(
q[i+1]-
q[i])
*(q[now+1]-
q[i]))
{
now++;
if(now==top+
1)now=
1;
}
ans=max(ans,dis2(
q[now]-
q[i]));
}
}
int main()
{
n=
read();
for(
int i=
1;i<=n;i++)
p[i].
x=
read(),p[i].
y=
read();
graham();
RC();
printf(
"%d",(
int)ans);
return 0;
}
旋转卡壳
题：
bzoj1185 bzoj1069
bzoj1069
题意：
在某块平面土地上有N个点，你可以选择其中的任意四个点，将这片土地围起来，当然，你希望这四个点围成的多边形面积最大。
分析：
先求凸包。 不规则四边形无法计算面积。便将其切成两个三角形。 朴素做法：枚举对角线
O(n2)
再枚举对角线两边的点
O(n)
总时间复杂度是$O(n^3)显然爆炸！
有一个奇怪的定理（不会证）：两边的要求的点（构成最大面积的）会跟对角线旋转的方向一起在凸包上同向旋转。
高级做法：枚举对角线一端，在枚举另外一端时，我们所要求的两个点就无需全部枚举（详见代码~）这样时间复杂度就为
O(n2)
了。
q[top+1]=a[
1];
double res=
0;
for (
int i=
1;i<=top;i++){
int a=i
%top+
1,b=(i+
2)
%top+
1;
for (
int j=i+
2;j<=top;j++){
while (a
%top+
1!=j && cro(
q[j],
q[a],
q[i])<cro(
q[j],
q[a+1],
q[i]))
a=a
%top+
1;
while (b
%top+
1!=i && cro(
q[b],
q[j],
q[i])<cro(
q[b+1],
q[j],
q[i]))
b=b
%top+
1;
res=max(res,fabs(cro(
q[i],
q[j],
q[a]))+fabs(cro(
q[i],
q[j],
q[b])));
}
}
return res;
bzoj1185
题意：
求一个最小的矩形包含所有的点。一共50000个点。
分析：
超神题解 先求凸包。 有一个奇怪的定理（不会证）：凸包上的一条边一定与矩形的一条边重合。 枚举凸包上的每一条边，现在我们只有求出矩形的最右边的点、最左边的点和最上边点就好了。注意到这三个点也是随枚举的边旋转而同向旋转的哦~这然后在纸上瞎推推就可以鸟~~
模板
using namespace std;
const
int N=
1001000;
const double eps=
0.
000000001;
int n,top;
double ansmj;
struct node{
double
x,
y;
node(){}
node(double _x,double _y):
x(_x),
y(_y){}
friend bool operator < (node a,node b){
if (fabs(a.
y-b.
y)<eps)
return a.
x<b.
x;
return a.
y<b.
y;
}
friend node operator + (node a,node b){
return node(a.
x+b.
x,a.
y+b.
y);
}
friend node operator - (node a,node b){
return node(a.
x-b.
x,a.
y-b.
y);
}
friend double dis (node a){
return sqrt(a.
x*a.
x+a.
y*a.
y);
}
friend double operator * (node a,node b){
return a.
x*b.
y-a.
y*b.
x;
}
friend double operator / (node a,node b){
return a.
x*b.
x+a.
y*b.
y;
}
friend node operator * (node a,double
x){
return node(a.
x*x,a.
y*x);
}
}
q[N],a[N],ans[
4];
bool cmp(node aa,node b){
double cro=(aa-a[
1])
*(b-a[
1]);
if (fabs(cro)<eps)
return dis(a[
1]-aa)<dis(a[
1]-b);
return cro>
0;
}
void graham(){
int id=
1;
for (
int i=
2;i<=n;i++)
if (a[i]<a[id])
id=i;
swap(a[
1],a[id]);
sort(a+
2,a+n+
1,cmp);
for (
int i=
1;i<=n;i++){
while (top>
1 && (
q[top]-
q[top-1])
*(a[i]-
q[top])<eps) top--;
q[++top]=a[i];
}
q[0]=
q[top];
}
void gao(){
int l=
1,r=
1,h=
1;
double L,R,H,D;
for (
int i=
0;i<top;i++){
D=dis(
q[i]-
q[i+1]);
while ((
q[i+1]-
q[i])
*(q[h+1]-
q[i])>(
q[i+1]-
q[i])
*(q[h]-
q[i])-eps) h=(h+
1)
%top;
while ((
q[i+1]-
q[i])/(
q[r+1]-
q[i])>(
q[i+1]-
q[i])/(
q[r]-
q[i])-eps) r=(r+
1)
%top;
if (i==
0) l=r;
while ((
q[i+1]-
q[i])/(
q[l+1]-
q[i])<(
q[i+1]-
q[i])/(
q[l]-
q[i])+eps) l=(l+
1)
%top;
L=(
q[i+1]-
q[i])/(
q[l]-
q[i])/D;
R=(
q[i+1]-
q[i])/(
q[r]-
q[i])/D;
H=(
q[i+1]-
q[i])
*(q[h]-
q[i])/D;
H=fabs(H);
double mianji=(R-L)
*H;
if (ansmj>mianji){
ansmj=mianji;
ans[
0]=
q[i]+(
q[i+1]-
q[i])
*(R/D);
ans[
1]=ans[
0]+(
q[r]-ans[
0])
*(H/dis(
q[r]-ans[
0]));
ans[
2]=ans[
1]-(ans[
0]-
q[i])
*((R-L)/dis(
q[i]-ans[
0]));
ans[
3]=ans[
2]-(ans[
1]-ans[
0]);
}
}
}
int main(){
freopen(
"a.in",
"r",stdin);
scanf(
"%d",&n);
for (
int i=
1;i<=n;i++)
scanf(
"%lf%lf",&a[i].
x,&a[i].
y);
graham();ansmj=
213333333333333;
gao();
printf(
"%.5lf\n",ansmj);
int mi=
0;
for (
int i=
0;i<=
3;i++)
if (ans[i]<ans[mi])
mi=i;
for (
int i=
0;i<=
3;i++){
printf(
"%.5lf %.5lf\n",ans[mi].
x,ans[mi].
y);
mi=(mi+
1)
%4;
}
}
半平面交
题：
bzoj2618YES bzoj3190 bzoj2732YES bzoj1038YES bzoj1007YES bzoj1137YES bzoj3800
bzoj2618
题意：
给出多个凸多边形，顶点按逆时针给出。求它们的重叠面积。
分析：
直接用半平面交乱搞就好了。当模板题。
模板
using namespace std;
const
int N=
1001000;
int n,cnt,tot;
double ans;
struct node{
double
x,
y;
node(){}
node(double _x,double _y):
x(_x),
y(_y){}
friend node operator - (node a,node b){
return node(a.
x-b.
x,a.
y-b.
y);
}
friend node operator + (node a,node b){
return node(a.
x+b.
y,a.
y+b.
y);
}
friend double operator * (node a,node b){
return a.
x*b.
y-a.
y*b.
x;
}
friend double slope (node a,node b){
return atan2(a.
y-b.
y,a.
x-b.
x);
}
}p[N],a[N];
struct line{
node st,ed;
double sl;
friend bool operator < (line a,line b){
if (a.sl==b.sl)
return (a.ed-a.st)
*(b.ed-a.st)>
0;
return a.sl<b.sl;
}
}b[N],
q[N];
node jiaodian(line a,line b){
double k1,k2,t;
k1=(b.ed-a.st)
*(a.ed-a.st);
k2=(a.ed-a.st)
*(b.st-a.st);
t=k1/(k1+k2);
node ans;
ans.
x=b.ed.
x+(b.st.
x-b.ed.
x)
*t;
ans.
y=b.ed.
y+(b.st.
y-b.ed.
y)
*t;
return ans;
}
int onleft(line a,line b,line k){
node dian=jiaodian(a,b);
return (k.ed-k.st)
*(dian-k.st)<
0;
}
void jiao(){
sort(b+
1,b+cnt+
1);
for (
int i=
1;i<=cnt;i++){
if (b[i].sl!=b[i-
1].sl)
tot++;
b[tot]=b[i];
}cnt=tot;tot=
0;
int l=
1,r=
0;
for (
int i=
1;i<=cnt;i++){
while (l<r && onleft(
q[r-1],
q[r],b[i])) r--;
while (l<r && onleft(
q[l+1],
q[l],b[i])) l++;
q[++r]=b[i];
}
while (l<r && onleft(
q[r-1],
q[r],b[l])) r--;
while (l<r && onleft(
q[l+1],
q[l],b[r])) l++;
q[r+1]=
q[l];
for (
int i=l;i<=r;i++)
p[++tot]=jiaodian(
q[i],
q[i+1]);
}
void getans(){
if (tot<
3)
return;
p[++tot]=p[
1];
for (
int i=
1;i<=tot;i++)
ans+=p[i]
*p[i+
1];
ans=fabs(ans)/
2.0;
}
int main(){
freopen(
"a.in",
"r",stdin);
freopen(
"my.out",
"w",stdout);
int T;scanf(
"%d",&T);
while (T--){
scanf(
"%d",&n);
for (
int i=
1;i<=n;i++)
scanf(
"%lf%lf",&a[i].
x,&a[i].
y);
a[n+
1]=a[
1];
for (
int i=
1;i<=n;i++){
b[++cnt].st=a[i];
b[cnt].ed=a[i+
1];
b[cnt].sl=slope(a[i+
1],a[i]);
}
}
jiao();
getans();
printf(
"%.3lf\n",ans);
}
