计算几何 多边形相交、半平面交

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<complex>
#include<vector>
#include<deque>
using namespace std;
typedef long long LL;
#define INF 0x7fffffff
#define zero(x) (((x)>0?(x):(-x))<eps)
const double eps=1e-8;
const double pi=acos(-1.0);
int dcmp(double x) { return x<-eps?-1:x>eps?1:0;}
double sqr(double x) { return x*x;}
double mysqrt(double n) { return sqrt(max(0.0,n));}
struct point
{
double x,y;
point() {};
point(double a,double b):x(a),y(b) {};
};
typedef point Vector;
//向量-向量
Vector operator -(const Vector &a, const Vector &b) {return Vector(a.x-b.x, a.y-b.y);}
//向量+向量
Vector operator +(const Vector &a, const Vector &b) {return Vector(a.x+b.x, a.y+b.y);}
//向量*常数
Vector operator *(const double &a, const Vector &b) {return Vector(a*b.x, a*b.y);}
Vector operator *(const Vector &a, const double &b) {return Vector(a.x*b, a.y*b);}
Vector operator /(const Vector &a, const double &b) {return Vector(a.x/b,a.y/b);}
//向量*向量 Dot
double dot(const Vector &a,const Vector &b) {return a.x*b.x+a.y*b.y;}
//向量X向量
double cross(const Vector &a,const Vector &b) {return a.x*b.y-a.y*b.x;}
//向量==向量
bool isequal(const Vector &a,const Vector &b) {return dcmp(a.x-b.x)==0&&dcmp(a.y-b.y)==0;}
double Area(vector<point> p)
{
int n=p.size();
double area = 0;
for(int i=1; i<n-1; ++i)
area += cross(p[i]-p[0], p[i+1]-p[0]);
return fabs(area/2);
}
//struct halfplane
//{
//
point a,b;
//
halfplane() {};
//
halfplane(point a,point b):a(a),b(b) {};
//};

typedef pair<point,point> halfplane;
inline double satisfy(point a,halfplane p)
{
return dcmp(cross(a-p.first,p.second-p.first))<=0;
}
point crosspoint(const halfplane &a,const halfplane &b)
{
double k=cross(b.first-b.second,a.first-b.second);
k=k/(k-cross(b.first-b.second,a.second-b.second));
return a.first+(a.second-a.first)*(k);
}
double arg(point p)
{
return arg(complex<double>(p.x,p.y));
}
bool cmp(const halfplane &a,const halfplane &b)
{
int res=dcmp(arg(a.second-a.first)-arg(b.second-b.first));
return res==0? satisfy(a.first,b):res<0;
}
vector<point> halfplaneIntersection(vector<halfplane> v)
{
sort(v.begin(),v.end(),cmp);
deque<halfplane> q;
deque<point> ans;
q.push_back(v[0]);
for(int i=1; i<v.size(); ++i)
{
if(dcmp(arg(v[i].second-v[i].first)-arg(v[i-1].second-v[i-1].first))==0)
{
continue;
}
while(ans.size()>0&&!satisfy(ans.back(),v[i]))
{
ans.pop_back();
q.pop_back();
}
while(ans.size()>0&&!satisfy(ans.front(),v[i]))
{
ans.pop_front();
q.pop_front();
}
ans.push_back(crosspoint(q.back(),v[i]));
q.push_back(v[i]);
}
while(ans.size()>0&&!satisfy(ans.back(),q.front()))
{
ans.pop_back();
q.pop_back();
}
while(ans.size()>0&&!satisfy(ans.front(),q.back()))
{
ans.pop_front();
q.pop_front();
}
ans.push_back(crosspoint(q.back(),q.front()));
return vector<point>(ans.begin(),ans.end());
}
vector<halfplane> hp;
vector<point> ans;
point p[100],q[100];
int main()
{
double x1,Y1,x2,Y2;
double x3,Y3,x4,Y4;
while(scanf("%lf %lf %lf %lf",&x1,&Y1,&x2,&Y2)!=EOF)
{
scanf("%lf %lf %lf %lf",&x3,&Y3,&x4,&Y4);
p[0]=point(x1,Y1);
p[1]=point(x2,Y1);
p[2]=point(x1,Y2);
hp.clear();
//要逆时针插入
if(x1>x2&&Y1>Y2) {
hp.push_back(halfplane(p[0],p[1]));
hp.push_back(halfplane(p[1],p[2]));
hp.push_back(halfplane(p[2],p[0]));
}
else if(x1>x2&&Y1<Y2) {
hp.push_back(halfplane(p[1],p[0]));
hp.push_back(halfplane(p[0],p[2]));
hp.push_back(halfplane(p[2],p[1]));
}
else if(x1<x2&&Y1>Y2) {
hp.push_back(halfplane(p[0],p[2]));
hp.push_back(halfplane(p[2],p[1]));
hp.push_back(halfplane(p[1],p[0]));
}
else if(x1<x2&&Y1<Y2) {
hp.push_back(halfplane(p[0],p[1]));
hp.push_back(halfplane(p[1],p[2]));
hp.push_back(halfplane(p[2],p[0]));
}
q[0]=point(x3,Y3);
q[1]=point(x4,Y3);
q[2]=point(x4,Y4);
q[3]=point(x3,Y4);
hp.push_back(halfplane(q[0],q[1]));
hp.push_back(halfplane(q[1],q[2]));
hp.push_back(halfplane(q[2],q[3]));
hp.push_back(halfplane(q[3],q[0]));
ans =halfplaneIntersection(hp);
printf("%.8fn",Area(ans));
}
return 0;
}