凸包：
https://blog.csdn.net/bone_ace/article/details/46239187
旋转卡壳算法：
https://blog.csdn.net/wang_heng199/article/details/74477738
http://www.cnblogs.com/xdruid/archive/2012/07/01/2572303.html
半平面交：
https://blog.csdn.net/commonc/article/details/55260747

POJ 1113 Wall（Graham模板）

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
typedef double D;
const D pi=acos(-1.0);
const int N=1002;
int n,k,i,top,st[N];
D L,ans;
struct P{
    int x,y;
    P(){};
    P(int xx,int yy){x=xx;y=yy;}
    friend P operator -(P a,P b){return P(a.x-b.x,a.y-b.y);}
    friend int operator ^(P a,P b){return a.x*b.y-a.y*b.x;}
}p[N];
int dir(P p,P p1,P p2){return (p1-p)^(p2-p);}
D dis (P p1,P p2){return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));}
bool cmp(P p1,P p2){
    int t=dir(p[0],p1,p2);
    return t>0 || t==0 && dis(p[0],p1)<dis(p[0],p2);
}
void graham(int n){
    if (n==1) top=0,st[0]=0;
    else{
        top=1;
        st[0]=0;st[1]=1;
        if (n>2){
            for (int i=2;i<n;i++){
                while (top && dir(p[st[top-1]],p[st[top]],p[i])<=0) top--;
                st[++top]=i;
            }
        }
    }
}
int main(){
    scanf("%d%lf",&n,&L);
    k=0;
    for (i=0;i<n;i++){
        scanf("%d%d",&p[i].x,&p[i].y);
        if (p[i].y<p[k].y || p[i].y==p[k].y && p[i].x<p[k].x) k=i;
    }
    swap(p[0],p[k]);
    sort(p+1,p+n,cmp);
    graham(n);
    for (i=0;i<top;i++) ans+=dis(p[st[i]],p[st[i+1]]);
    ans+=dis(p[st[0]],p[st[top]]);
    ans+=2*pi*L;
    printf("%d",(int)(ans+0.5));
}

POJ 1228 Grandpa’s Estate

//题意：原本有一些点围成了一个凸多边形，你不知道原来是什么样子的，
//现在又 给出一些点，确保这些点都是凸包上的点(不会在以前的凸包的里面)， 
//现在问你这些点围成的形状是否可以确定原来那些点围成的凸多边形
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
typedef double D;
int T,n,k,i,fl,top,st[1002];
struct P{
    int x,y;
    P(){};
    P(int xx,int yy){x=xx;y=yy;}
    friend P operator-(P p1,P p2){return P(p1.x-p2.x,p1.y-p2.y);}
    friend P operator*(P p1,P p2){return P(p1.x*p2.x,p1.y*p2.y);}
    friend int operator^(P p1,P p2){return p1.x*p2.y-p2.x*p1.y;}
}p[1002];
int dir(P p,P p1,P p2){return (p-p1)^(p-p2);}
bool on_seg(P p1,P p2,P p){
    return dir(p,p1,p2)==0 && min(p1.x,p2.x)<=p.x && p.x<=max(p1.x,p2.x)
    && min(p1.y,p2.y)<=p.y && p.y<=max(p1.y,p2.y);
}
D dis(P p1,P p2){P p=(p1-p2)*(p1-p2);return sqrt(p.x+p.y);}
bool cmp(P p1,P p2){
    int t=dir(p[0],p1,p2);
    return t>0 || t==0 && dis(p[0],p1)<dis(p[0],p2);
}
void graham(int n){
    top=1;
    st[0]=0;st[1]=1;
    for (int i=2;i<n;i++){
        while (top && dir(p[st[top-1]],p[st[top]],p[i])<=0) top--;
        st[++top]=i;
    }
}
bool check(P p1,P p2,int n){
    for (int i=0;i<n;i++)
        if (!(p1.x==p[i].x && p1.y==p[i].y || p2.x==p[i].x && p2.y==p[i].y) && on_seg(p1,p2,p[i])) return 1;
    return 0;
}
int main(){
    scanf("%d",&T);
    while (T--){
        scanf("%d",&n);
        k=0;
        for (i=0;i<n;i++){
            scanf("%d%d",&p[i].x,&p[i].y);
            if (p[i].y<p[k].y || p[i].y==p[k].y && p[i].x<p[k].x) k=i;
        }
        if (n<6){
            puts("NO");
            continue;
        }
        swap(p[0],p[k]);
        sort(p+1,p+n,cmp);
        graham(n);
        if (top>=2) fl=1;
        for (i=0;i<top && fl;i++)
            if (!check(p[st[i]],p[st[i+1]],n)) fl=0;
        if (!check(p[st[top]],p[st[0]],n)) fl=0;
        puts(fl?"YES":"NO");
    }
}

POJ 3348 Cows

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
typedef double D;
const int N=10002;
int n,k,i,top,st[N];
D ans;
struct P{
    int x,y;
    P(){};
    P(int xx,int yy){x=xx;y=yy;}
    friend P operator -(P a,P b){return P(a.x-b.x,a.y-b.y);}
    friend int operator ^(P a,P b){return a.x*b.y-a.y*b.x;}
}p[N];
int dir(P p,P p1,P p2){return (p1-p)^(p2-p);}
D dis (P p1,P p2){return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));}
bool cmp(P p1,P p2){
    int t=dir(p[0],p1,p2);
    return t>0 || t==0 && dis(p[0],p1)<dis(p[0],p2);
}
void graham(int n){
    if (n==1) top=0,st[0]=0;
    else{
        top=1;
        st[0]=0;st[1]=1;
        if (n>2){
            for (int i=2;i<n;i++){
                while (top && dir(p[st[top-1]],p[st[top]],p[i])<=0) top--;
                st[++top]=i;
            }
        }
    }
}
int main(){
    scanf("%d",&n);
    k=0;
    for (i=0;i<n;i++){
        scanf("%d%d",&p[i].x,&p[i].y);
        if (p[i].y<p[k].y || p[i].y==p[k].y && p[i].x<p[k].x) k=i;
    }
    swap(p[0],p[k]);
    sort(p+1,p+n,cmp);
    graham(n);
    st[++top]=0;
    for (i=0;i<top;i++) ans+=dir(p[0],p[st[i]],p[st[i+1]]);
    printf("%d",(int)ans/100);
}

poj 2187 Beauty Contest（旋转卡壳模板）

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
typedef double D;
const int N=50002;
const D eps=1e-8;
int k,top,i,st[N],n;
struct P{
    D x,y;
    P(){};
    P(D xx,D yy){x=xx;y=yy;}
    friend P operator+(P p1,P p2){return P(p1.x+p2.x,p1.y+p2.y);}
    friend P operator-(P p1,P p2){return P(p1.x-p2.x,p1.y-p2.y);}
    friend P operator*(P p1,P p2){return P(p1.x*p2.x,p1.y*p2.y);}
    friend D operator^(P p1,P p2){return p1.x*p2.y-p2.x*p1.y;}
}p[N];
int sgn(D x){
    if (fabs(x)<eps) return 0;
    if (x>0) return 1;
    return -1;
}
D dir(P p,P p1,P p2){return (p-p1)^(p-p2);}
D dis(P p1,P p2){P p=(p1-p2)*(p1-p2);return sqrt(p.x+p.y);}
D DIS(P p1,P p2){P p=(p1-p2)*(p1-p2);return p.x+p.y;}
D disl(P p,P p1,P p2){return fabs(dir(p,p1,p2))/dis(p1,p2);}//要加fabs 
bool cmp(P p1,P p2){
    int t=dir(p[0],p1,p2);
    return t>0 || t==0 && dis(p[0],p1)<dis(p[0],p2);
}
void graham(int n){
    if (n==1) top=0,st[0]=0;
    else{
        top=1;
        st[0]=0;st[1]=1;
        if (n>2){
            for (int i=2;i<n;i++){
                while (top && dir(p[st[top-1]],p[st[top]],p[i])<=0) top--;
                st[++top]=i;
            }
        }
    }
}
D RC(int n){
    if (n==1) return 0;
    if (n==2) return DIS(p[st[0]],p[st[1]]);//刚开始写成dis(p[0],p[1]) 
    int now=1;
    D ans=0;
    st[n]=0;//搞一个环，方便处理 
    for (int i=0;i<n;i++){
        while (sgn(disl(p[st[now]],p[st[i]],p[st[i+1]])-disl(p[st[now+1]],p[st[i]],p[st[i+1]]))<=0) now=(now+1)%n;
        ans=max(ans,max(DIS(p[st[now]],p[st[i]]),DIS(p[st[now]],p[st[i+1]])));
    }
    return ans;
}
int main(){
    scanf("%d",&n);
    k=0;
    for (i=0;i<n;i++){
        scanf("%lf%lf",&p[i].x,&p[i].y);
        if (p[i].y<p[k].y || p[i].y==p[k].y && p[i].x<p[k].x) k=i;
    }
    swap(p[0],p[k]);
    sort(p+1,p+n,cmp);
    graham(n);
    printf("%.0f",RC(top+1));//加1 
}

hdu2907

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
typedef double D;
const int N=32;
int n,k,i,top,st[N],T,pp,qq,ao,ha[N];
struct P{
    int x,y,id;
    P(){};
    P(int xx,int yy,int iid){x=xx;y=yy;id=iid;}
    friend P operator -(P a,P b){return P(a.x-b.x,a.y-b.y,0);}
    friend int operator ^(P a,P b){return a.x*b.y-a.y*b.x;}
}p[N];
int dir(P p,P p1,P p2){return (p1-p)^(p2-p);}
D dis (P p1,P p2){return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));}
bool cmp(P p1,P p2){
    int t=dir(p[0],p1,p2);
    return t>0 || t==0 && dis(p[0],p1)<dis(p[0],p2);
}
void graham(int n){
    if (n==1) top=0,st[0]=0;
    else{
        top=1;
        st[0]=0;st[1]=1;
        if (n>2){
            for (int i=2;i<n;i++){
                while (top && dir(p[st[top-1]],p[st[top]],p[i])<=0) top--;
                st[++top]=i;
            }
        }
    }
}
int main(){
    scanf("%d",&T);
    while (T--){
        scanf("%d%d%d",&pp,&qq,&n);
        k=0;ao=0;memset(ha,0,sizeof(ha));
        for (i=0;i<n;i++){
            scanf("%d%d",&p[i].x,&p[i].y);p[i].id=i;
            if (p[i].y<p[k].y || p[i].y==p[k].y && p[i].x<p[k].x) k=i;
        }
        swap(p[0],p[k]);
        sort(p+1,p+n,cmp);
        graham(n);
        for (i=0;i<=top;i++) ha[p[st[i]].id]=1;
        ha[n]=ha[0];
        for (i=0;i<n;i++)
            if (ha[i] && !ha[i+1]) ao++;
        printf("%d\n",max((top+1)*qq-(pp+qq)*ao,0));
    }
}

HDU 1632 Polygons

#include<bits/stdc++.h>
using namespace std;
typedef double D;
const int N=100002;
D x,y,S;
int m,n,tot,i,st;
struct P{
    D x,y;
    P(){};
    P(D xx,D yy){x=xx;y=yy;}
    friend P operator-(P a,P b){return P(a.x-b.x,a.y-b.y);}
    friend D operator^(P a,P b){return a.x*b.y-a.y*b.x;}
    friend P operator*(D t,P p){return P(p.x*t,p.y*t);}
    friend P operator+(P a,P b){return P(a.x+b.x,a.y+b.y);}
}p[N],a[N];
D dir(P p,P p1,P p2){return (p1-p)^(p2-p);}
struct L{
    P p,v;D slop;
    L(){};
    L(P x,P y,D ss){p=x;v=y;slop=ss;}
}l[N],s[N];
bool Pleft(P p,L x){return ((p-x.p)^x.v)>=0;}
bool Lleft(L x,L y){
    D t=x.v^y.v;
    return t>0 || t==0 && (x.v^(y.p-x.p))>0;
}
P inter(L x,L y){
    P u=x.p-y.p;
    return (u^y.v)/(y.v^x.v)*x.v+x.p;
}
bool cmp(L a,L b){
    return a.slop!=b.slop?a.slop<b.slop:(a.v^(b.v+b.p-a.p))>0;
}
D hpi(){
    sort(l+1,l+m+1,cmp);
    int tp=0;
    for (int i=1;i<=m;i++){
        if (i==1 || (l[i].v^l[i-1].v)!=0) tp++;
        l[tp]=l[i];
    }
    m=tp;
    int L=1,R=2;
    s[1]=l[1];s[2]=l[2];
    for (int i=3;i<=m;i++){
        while (L<R && Pleft(inter(s[R],s[R-1]),l[i])) R--;
        while (L<R && Pleft(inter(s[L],s[L+1]),l[i])) L++;
        s[++R]=l[i];
    }
    while (L<R && Pleft(inter(s[R],s[R-1]),s[L])) R--;
    if (R-L<=1) return 0;
    s[L-1]=s[R];tp=0;
    for (int i=L;i<=R;i++) a[++tp]=inter(s[i],s[i-1]);
    D ans=0;
    for (int i=3;i<=tp;i++) ans+=dir(a[1],a[i-1],a[i]);
    return ans;
}
int main(){
    while (~scanf("%d",&n) && n){
        S=m=tot=0;st=tot+1;
        while (n--){
            scanf("%lf%lf",&x,&y);
            p[++tot]=P(x,y);
            if (tot>st) l[++m]=L(p[tot],p[tot-1]-p[tot],atan2((p[tot-1]-p[tot]).y,(p[tot-1]-p[tot]).x));
        }
        l[++m]=L(p[st],p[tot]-p[st],atan2((p[tot]-p[st]).y,(p[tot]-p[st]).x));
        for (i=st+2;i<=tot;i++) S-=dir(p[st],p[i-1],p[i]);
        scanf("%d",&n);
        st=tot+1;
        while (n--){
            scanf("%lf%lf",&x,&y);
            p[++tot]=P(x,y);
            if (tot>st) l[++m]=L(p[tot],p[tot-1]-p[tot],atan2((p[tot-1]-p[tot]).y,(p[tot-1]-p[tot]).x));
        }
        l[++m]=L(p[st],p[tot]-p[st],atan2((p[tot]-p[st]).y,(p[tot]-p[st]).x));
        for (i=st+2;i<=tot;i++) S-=dir(p[st],p[i-1],p[i]);
        printf("%8.2f",S/2-hpi());//不能换行 
    }
    puts("");//最后一定要换行，格式很严格 
}

bzoj2618（半平面交模板）

//https://www.cnblogs.com/acha/p/6481100.html有错误，但可以提供一个思路
//http://hzwer.com/4713.html 
#include<bits/stdc++.h>
using namespace std;
typedef double D;
int T,z,x,y,st,n,m;
struct P{
    D x,y;
    P(){};
    P(D xx,D yy){x=xx;y=yy;}
    friend P operator+(P p1,P p2){return P(p1.x+p2.x,p1.y+p2.y);}
    friend P operator-(P p1,P p2){return P(p1.x-p2.x,p1.y-p2.y);}
    friend D operator^(P p1,P p2){return p1.x*p2.y-p2.x*p1.y;}
    friend P operator*(D t,P p){return P(p.x*t,p.y*t);}
    friend P operator/(P p,D t){return P(p.x/t,p.y/t);}
}p[502],a[502];
D dir(P p,P p1,P p2){return (p-p1)^(p-p2);}
struct L{
    P p,v;D slop;
    L(){};
    L(P xx,P yy,D ss){p=xx;v=yy;slop=ss;}
}l[502],s[502];
bool Pleft(P x,L y){return ((x-y.p)^y.v)>=0;}//判断x是否在y左侧或在y上 
bool Lleft(L x,L y){//判断x是否在y逆时针方向 
    int t=x.v^y.v;
    return t>0 || t==0 && (x.v^(y.p-x.p))>0;
}
P inter(L x,L y){//求交点，可画图理解，就是根据面积比和相似来计算的，不难 
    P u=x.p-y.p;
    return (u^y.v)/(y.v^x.v)*x.v+x.p;//叉积顺序要注意，两个面积应该相除应该是正数，如果搞不清可以用abs 
}
bool cmp(L a,L b){
    return a.slop!=b.slop?a.slop<b.slop:(a.v^(b.v+b.p-a.p))>0;
}
D hpi(){//half-plane intersection 
    sort(l+1,l+m+1,cmp);//按向量从左到右排序 
    int tp=0;
    for (int i=1;i<=m;i++){
        if (i==1 || (l[i].v^l[i-1].v)!=0) tp++;//不平行 
        l[tp]=l[i];
    }
    m=tp;
    int L=1,R=2;
    s[1]=l[1];s[2]=l[2];
    for (int i=3;i<=m;i++){
        while (L<R && Pleft(inter(s[R],s[R-1]),l[i])) R--;
        while (L<R && Pleft(inter(s[L],s[L+1]),l[i])) L++;
        s[++R]=l[i];
    }
    while (L<R && Pleft(inter(s[R],s[R-1]),s[L])) R--;//删除无用平面 
    while (L<R && Pleft(inter(s[L],s[L+1]),s[R])) L++;
    if (R-L<=1) return 0;//点或线，无面积 
    tp=0;
    s[L-1]=s[R];
    for (int i=L;i<=R;i++) a[++tp]=inter(s[i],s[i-1]);//转凸包 
    D ans=0;
    for (int i=3;i<=tp;i++) ans+=dir(a[1],a[i-1],a[i]);
    return ans/2;
}
int main(){
    scanf("%d",&T);
    while (T--){
        scanf("%d",&z);
        st=n+1;
        while (z--){
            scanf("%d%d",&x,&y);
            p[++n]=P(x,y);
            if (n>st) l[++m]=L(p[n-1],p[n]-p[n-1],atan2((p[n]-p[n-1]).y,(p[n]-p[n-1]).x));
        }
        l[++m]=L(p[n],p[st]-p[n],atan2((p[st]-p[n]).y,(p[st]-p[n]).x));
    }
    printf("%.3lf",hpi());
}

计算几何2

POJ 1113 Wall（Graham模板）

POJ 1228 Grandpa’s Estate

POJ 3348 Cows

poj 2187 Beauty Contest（旋转卡壳模板）

hdu2907

HDU 1632 Polygons

bzoj2618（半平面交模板）