给出三个半平面交的裸题。
不会的上百度上谷（gu）歌（gou）一下。
毕竟学长的语文是体育老师教的。(卡格玩笑，别当真。)
这种东西明白就好，代码可以当模板。
//poj1474 Video Surveillance
//点集默认顺时针
//算法参考：http://www.cnblogs.com/huangxf/p/4067763.html
#include<cstdio>
#include<cmath>
using namespace std;
const int N=1e5+;
struct point{
double x,y;
}p[N],tmp[N],q[N];
double a,b,c;int cas,n,m;
void get_line(point p1,point p2){
a=p2.y-p1.y;
b=p1.x-p2.x;
c=p2.x*p1.y -p2.y*p1.x;
}
point cross(point p1,point p2){
double u=fabs(a*p1.x+b*p1.y+c);
double v=fabs(a*p2.x+b*p2.y+c);
point ret;
ret.x=(v*p1.x+u*p2.x)/(u+v);
ret.y=(v*p1.y+u*p2.y)/(u+v);
return ret;
}
void cut(){
int tm=;//顺时针都是> or >=;否则都取反
for(int i=;i<=m;i++){
if(a*q[i].x+b*q[i].y+c>=){
// c由于精度问题，可能会偏小，所以有些点本应在右侧而没在，故应该接着判断
tmp[++tm]=q[i];
}
else{
if(a*q[i-].x+b*q[i-].y+c>)
//如果p[i-1]在直线的右侧的话，则将p[i],p[i-1]形成的直线与已知直线的交点作为核的一个顶点
//(这样的话，由于精度的问题，核的面积可能会有所减少)
tmp[++tm]=cross(q[i-],q[i]);
if(a*q[i+].x+b*q[i+].y+c>)
tmp[++tm]=cross(q[i],q[i+]);
}
}
for(int i=;i<=tm;i++) q[i]=tmp[i];//将tmp中暂存的核的顶点转移到q中
q[]=q[tm];q[tm+]=q[];m=tm;
}
void solve(){
for(int i=;i<=n;i++) q[i]=p[i];
q[]=p[n];q[n+]=q[];p[n+]=p[];
//读入的多边形的顶点（顺时针）、p为存放最终切割得到的多边形顶点的数组、暂存核的顶点
m=n;//m为最终切割得到的多边形的顶点数，将其初始化为多边形的顶点的个数
for(int i=;i<=n;i++){
get_line(p[i],p[i+]);
cut();
}
}
int main(){
for(cas=;~scanf("%d",&n)&&n;cas++){
for(int i=;i<=n;i++) scanf("%lf%lf",&p[i].x,&p[i].y);
solve();
printf("Floor #%d\nSurveillance is ",cas);
puts(m?"possible.\n":"impossible.\n");
}
return ;
}
以下同理
//poj3335 Rotating Scoreboard
//点集默认顺时针
#include<cstdio>
#include<cmath>
using namespace std;
const int N=1e5+;
struct point{
double x,y;
}p[N],tmp[N],q[N];
double a,b,c;int cas,n,m;
void get_line(point p1,point p2){
a=p2.y-p1.y;
b=p1.x-p2.x;
c=p2.x*p1.y -p2.y*p1.x;
}
point cross(point p1,point p2){
double u=fabs(a*p1.x+b*p1.y+c);
double v=fabs(a*p2.x+b*p2.y+c);
point ret;
ret.x=(v*p1.x+u*p2.x)/(u+v);
ret.y=(v*p1.y+u*p2.y)/(u+v);
return ret;
}
void cut(){
int tm=;
for(int i=;i<=m;i++){
if(a*q[i].x+b*q[i].y+c>=){
tmp[++tm]=q[i];
}
else{
if(a*q[i-].x+b*q[i-].y+c>)
tmp[++tm]=cross(q[i-],q[i]);
if(a*q[i+].x+b*q[i+].y+c>)
tmp[++tm]=cross(q[i],q[i+]);
}
}
for(int i=;i<=tm;i++) q[i]=tmp[i];
q[]=q[tm];q[tm+]=q[];m=tm;
}
void solve(){
for(int i=;i<=n;i++) q[i]=p[i];
q[]=p[n];q[n+]=q[];p[n+]=p[];
m=n;
for(int i=;i<=n;i++){
get_line(p[i],p[i+]);
cut();
}
}
int main(){
for(scanf("%d",&cas);cas--;){
scanf("%d",&n);
for(int i=;i<=n;i++) scanf("%lf%lf",&p[i].x,&p[i].y);
solve();
puts(m?"YES":"NO");
}
return ;
}
//poj3130 How I Mathematician Wonder What You Are!
//点集默认逆时针
#include<cstdio>
#include<cmath>
using namespace std;
const int N=1e5+;
struct point{
double x,y;
}p[N],tmp[N],q[N];
double a,b,c;int cas,n,m;
void get_line(point p1,point p2){
a=p2.y-p1.y;
b=p1.x-p2.x;
c=p2.x*p1.y -p2.y*p1.x;
}
point cross(point p1,point p2){
double u=fabs(a*p1.x+b*p1.y+c);
double v=fabs(a*p2.x+b*p2.y+c);
point ret;
ret.x=(v*p1.x+u*p2.x)/(u+v);
ret.y=(v*p1.y+u*p2.y)/(u+v);
return ret;
}
void cut(){
int tm=;
for(int i=;i<=m;i++){
if(a*q[i].x+b*q[i].y+c<=){
tmp[++tm]=q[i];
}
else{
if(a*q[i-].x+b*q[i-].y+c<)
tmp[++tm]=cross(q[i-],q[i]);
if(a*q[i+].x+b*q[i+].y+c<)
tmp[++tm]=cross(q[i],q[i+]);
}
}
for(int i=;i<=tm;i++) q[i]=tmp[i];
q[]=q[tm];q[tm+]=q[];m=tm;
}
void solve(){
for(int i=;i<=n;i++) q[i]=p[i];
q[]=p[n];q[n+]=q[];p[n+]=p[];
m=n;
for(int i=;i<=n;i++){
get_line(p[i],p[i+]);
cut();
}
}
int main(){
while(scanf("%d",&n)==&&n){
for(int i=;i<=n;i++) scanf("%lf%lf",&p[i].x,&p[i].y);
solve();
puts(m?"":"");
}
return ;
}