逆时针给出线段,如果模板是顺时针的修改下系数的符号进行平面交即可。
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<vector>
#include<cmath>
#include<queue>
#include<set>
using namespace std;
#define N 20100
#define LL long long
#define INF 0xfffffff
const double eps = 1e-;
const double pi = acos(-1.0);
const double inf = ~0u>>;
int m;
int cCnt,curCnt;
struct point
{
double x,y;
point(double x=,double y = ):x(x),y(y) {}
};
point points[N],p[N],q[N];
void getline(point x,point y,double &a,double &b,double &c)
{
a = x.y - y.y;
b = y.x - x.x;
c = x.x * y.y-y.x * x.y;
}
void initial()
{
for(int i = ; i <= m; ++i)p[i] = points[i];
p[m+] = p[];
p[] = p[m];
cCnt = m;
}
point intersect(point x,point y,double a,double b,double c)
{
double u = fabs(a * x.x + b * x.y + c);
double v = fabs(a * y.x + b * y.y + c);
point pt;
pt.x=(x.x * v + y.x * u) / (u + v);
pt.y=(x.y * v + y.y * u) / (u + v);
return pt;
}
void cut(double a,double b ,double c)
{
curCnt = ;
for(int i = ; i <= cCnt; ++i)
{
if(a*p[i].x + b*p[i].y + c >= )q[++curCnt] = p[i];
else
{
if(a*p[i-].x + b*p[i-].y + c > )
q[++curCnt] = intersect(p[i],p[i-],a,b,c);
if(a*p[i+].x + b*p[i+].y + c > )
q[++curCnt] = intersect(p[i],p[i+],a,b,c);
}
}
for(int i = ; i <= curCnt; ++i)p[i] = q[i];
p[curCnt+] = q[];
p[] = p[curCnt];
cCnt = curCnt;
}
void solve()
{
double area = ;
for(int i = ; i <= cCnt; ++i)
area += p[i].x * p[i + ].y - p[i + ].x * p[i].y;
area = fabs(area / 2.0);
printf("%.1f\n",area); }
void GuiZhengHua()
{
//规整化方向,逆时针变顺时针,顺时针变逆时针
for(int i = ; i < (m+)/; i ++)
swap(points[i], points[m-i]);
}
int main()
{
points[] = point(,);
points[] = point(,);
points[] = point(,);
points[] = point(,);
points[] = p[];
int n,i;
while(scanf("%d",&n)!=EOF)
{
m = ;
initial();
for(i = ; i <= ; ++i)
{
double a,b,c;
getline(points[i],points[i+],a,b,c);
cut(a,b,c);
}
for(i = ; i <= *n ; i+=)
{
point p1,p2;
scanf("%lf%lf%lf%lf",&p1.x,&p1.y,&p2.x,&p2.y);
double a,b,c;
getline(p1,p2,a,b,c);
cut(a,b,c);
} // m = 2*n+4;
//GuiZhengHua();
//points[m+1] = points[1];
solve();
}
return ;
}