我是看了别人的博客学会的，所以没什么好说的。
就说说我对这个算法的看法吧，这算法的核心思想就是线性规划（Linear Programming）
运用在半平面中大概通俗来说是这样两个过程：
1、给出一些点组成一个多边形；
2、用直线去分割这个多边形。
好像没什么用处是吧。其实重要的是把问题抽象成这个样子。
然后适用范围还是挺广的，另外将此算法拓展一下就可以利用Voronoi图来解决一些问题。
关于学习半平面交，推荐下面两个链接，我就是看这两个博客入门的
http://www.cnblogs.com/ka200812/archive/2012/01/20/2328316.html（这个博主画了个图讲解，对半平面一窍不通的可以先看看这个）
http://blog.csdn.net/accry/article/details/6070621（这里有一些经典的例题，虽然可能他解释的不是很好，不过推荐做做这些题感受一下半平面交的应用）
学会了这个算法之后嘞，理论上来说，你就可以学会如何用最少的点火次数在一个理想条件下，
最快地烧掉学校啊，情敌的豪宅啊，之类的东西。
啊，大概就是这些了。
下面是我做的一些关于半平面交的代码，上面那个链接里都有，这个，可以参考参考
//poj3335
#include<iostream>
#include<map>
#include<string>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
struct dot
{
double x,y;
dot(){}
dot(double a,double b){x=a;y=b;}
dot operator +(dot a){return dot(x+a.x,y+a.y);}
dot operator -(dot a){return dot(x-a.x,y-a.y);}
double operator *(dot a){return x*a.y-y*a.x;}
double operator /(dot a){return x*a.x+y*a.y;}
bool operator ==(dot a){return x==a.x&&y==a.y;}
void in(){scanf("%lf%lf",&x,&y);}
void out(){printf("%lf %lf",x,y);}
double dis(dot a){return sqrt(pow(x-a.x,2)+pow(y-a.y,2));}
};
dot cross(dot a,dot b,dot c,dot d)
{
double e,f,g,h,i,j,k,l,m;
e=b.y-a.y;f=a.x-b.x;g=a.x*b.y-a.y*b.x;
h=d.y-c.y;i=c.x-d.x;j=c.x*d.y-c.y*d.x;
k=dot(e,h)*dot(f,i);
l=dot(g,j)*dot(f,i);
m=dot(e,h)*dot(g,j);
return dot(l/k,m/k);
}
bool work(dot *a,int n)
{
int i,j,k,m=n;
dot b[110],c[110],d;
memcpy(b,a,sizeof(b));
for(i=0;i<n;i++)
{
d=a[(i+1)%n]-a[i];
for(j=k=0;j<m;j++)
if(d*(b[j]-a[i])<=0)
c[k++]=b[j];
else
{
if(d*(b[(j-1+m)%m]-a[i])<0)
c[k++]=cross(a[i],a[(i+1)%n],b[(j-1+m)%m],b[j]);
if(d*(b[(j+1)%m]-a[i])<0)
c[k++]=cross(a[i],a[(i+1)%n],b[j],b[(j+1)%m]);
}
if(k==0)
return 0;
m=k;
for(j=0;j<m;j++)
b[j]=c[j];
}
return 1;
}
int main()
{
dot a[110];
int T,i,n;
cin>>T;
while(T--)
{
cin>>n;
for(i=0;i<n;i++)
a[i].in();
if(work(a,n))
printf("YES\n");
else
printf("NO\n");
}
}
//poj2540
#include<iostream>
#include<map>
#include<string>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
struct dot
{
double x,y;
dot(){}
dot(double a,double b){x=a;y=b;}
dot operator +(dot a){return dot(x+a.x,y+a.y);}
dot operator -(dot a){return dot(x-a.x,y-a.y);}
double operator *(dot a){return x*a.y-y*a.x;}
double operator /(dot a){return x*a.x+y*a.y;}
bool operator ==(dot a){return x==a.x&&y==a.y;}
dot mid(dot a){return dot((x+a.x)/2,(y+a.y)/2);}
void in(){scanf("%lf%lf",&x,&y);}
void out(){printf("%lf %lf",x,y);}
double mod(){return sqrt(x*x+y*y);}
double dis(dot a){return sqrt(pow(x-a.x,2)+pow(y-a.y,2));}
};
dot cross(dot a,dot b,dot c,dot d)
{
double e,f,g,h,i,j,k,l,m;
e=b.y-a.y;f=a.x-b.x;g=a.x*b.y-a.y*b.x;
h=d.y-c.y;i=c.x-d.x;j=c.x*d.y-c.y*d.x;
k=dot(e,h)*dot(f,i);
l=dot(g,j)*dot(f,i);
m=dot(e,h)*dot(g,j);
return dot(l/k,m/k);
}
double car(dot *a,int n)
{
int i;
double ans=0;
for(i=2;i<n;i++)
ans+=(a[i]-a[0])*(a[i-1]-a[0]);
return ans/2;
}
void cut(dot *a,int &n,dot b,dot c)
{
int i,j;
dot d[110];
for(i=j=0;i<n;i++)
{
if(c*(a[i]-b)<=0)
d[j++]=a[i];
else
{
if(c*(a[(i-1+n)%n]-b)<0)
d[j++]=cross(b,b+c,a[(i-1+n)%n],a[i]);
if(c*(a[(i+1)%n]-b)<0)
d[j++]=cross(b,b+c,a[(i+1)%n],a[i]);
}
}
n=j;
for(i=0;i<n;i++)
a[i]=d[i];
}
int main()
{
char s[100];
int n=4;
double ans;
dot a[110],b,c,d,e;
a[0]=dot(0,0);
a[1]=dot(0,10);
a[2]=dot(10,10);
a[3]=dot(10,0);
c=dot(0,0);
while(gets(s))
{
sscanf(s,"%lf%lf%s",&b.x,&b.y,s);
d=b-c;
e=dot(d.y,d.x);
if(strcmp(s,"Hotter")==0)
e.x=-e.x;
else if(strcmp(s,"Colder")==0)
e.y=-e.y;
else
n=0;
cut(a,n,b.mid(c),e);
ans=car(a,n);
c=b;
printf("%.2f\n",ans);
}
}
//poj1755
#include<iostream>
#include<map>
#include<string>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
const double inf=1e20;
struct dot
{
double x,y;
dot(){}
dot(double a,double b){x=a;y=b;}
dot operator +(dot a){return dot(x+a.x,y+a.y);}
dot operator -(dot a){return dot(x-a.x,y-a.y);}
dot operator *(double a){return dot(x*a,y*a);}
double operator *(dot a){return x*a.y-y*a.x;}
dot operator /(double a){return dot(x/a,y/a);}
double operator /(dot a){return x*a.x+y*a.y;}
bool operator ==(dot a){return x==a.x&&y==a.y;}
void in(){scanf("%lf%lf",&x,&y);}
void out(){printf("%lf %lf",x,y);}
double mod(){return sqrt(x*x+y*y);}
double dis(dot a){return sqrt(pow(x-a.x,2)+pow(y-a.y,2));}
};
dot cross(dot a,dot b,dot c,dot d)
{
double e,f,g,h,i,j,k,l,m;
e=b.y-a.y;f=a.x-b.x;g=a.x*b.y-a.y*b.x;
h=d.y-c.y;i=c.x-d.x;j=c.x*d.y-c.y*d.x;
k=dot(e,h)*dot(f,i);
l=dot(g,j)*dot(f,i);
m=dot(e,h)*dot(g,j);
return dot(l/k,m/k);
}
struct fun
{
double a,b,c;
fun(){}
fun(double x,double y,double z)
{
a=x;
b=y;
c=z;
}
void in(){scanf("%lf%lf%lf",&a,&b,&c);}
};
dot sf(fun a,fun b)
{
double c,d,e;
c=dot(a.a,b.a)*dot(a.b,b.b);
d=dot(a.c,b.c)*dot(a.b,b.b);
e=dot(a.a,b.a)*dot(a.c,b.c);
return dot(d/c,e/c);
}
fun cg(dot a,dot b){return fun(b.y-a.y,a.x-b.x,a.x*b.y-a.y*b.x);}
void cut(dot *a,int &n,fun b)
{
int i,j;
dot c[110];
for(i=j=0;i<n;i++)
{
if(a[i].x*b.a+a[i].y*b.b<b.c)
c[j++]=a[i];
else
{
if(a[(i-1+n)%n].x*b.a+a[(i-1+n)%n].y*b.b<b.c)
c[j++]=sf(cg(a[i],a[(i-1+n)%n]),b);
if(a[(i+1)%n].x*b.a+a[(i+1)%n].y*b.b<b.c)
c[j++]=sf(cg(a[i],a[(i+1)%n]),b);
}
}
n=j;
for(i=0;i<n;i++)
a[i]=c[i];
}
void init(dot *a,int &n)
{
n=4;
a[0]=dot(0,0);
a[1]=dot(0,inf);
a[2]=dot(inf,inf);
a[3]=dot(inf,0);
}
int main()
{
fun a[110],t;
dot b[110];
int n,i,j,m;
while(cin>>n)
{
for(i=0;i<n;i++)
a[i].in();
for(i=0;i<n;i++)
{
init(b,m);
for(j=0;j<n;j++)
{
if(i==j)
continue;
t=fun(1/a[i].a-1/a[j].a,1/a[i].b-1/a[j].b,1/a[j].c-1/a[i].c);
cut(b,m,t);
}
if(m==0)
printf("No\n");
else
printf("Yes\n");
}
}
}