hdu3060Area2(任意多边形相交面积)

链接

多边形的面积求解是通过选取一个点(通常为原点或者多边形的第一个点)和其它边组成的三角形的有向面积。

对于两个多边形的相交面积就可以通过把多边形分解为三角形,求出三角形的有向面积递加。三角形为凸多边形,因此可以直接用凸多边形相交求面积的模板。

凸多边形相交后的部分肯定还是凸多边形,所以只需要判断哪些点是相交部分上的点,最后求下面积。

 #include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<vector>
#include<cmath>
#include<queue>
#include<set>
using namespace std;
#define N 510
#define LL long long
#define INF 0xfffffff
const double eps = 1e-;
const double pi = acos(-1.0);
const double inf = ~0u>>;
struct point
{
double x,y;
point(double x=,double y=):x(x),y(y) {} //构造函数 方便代码编写
}p[N],q[N];
typedef point pointt;
pointt operator + (point a,point b)
{
return point(a.x+b.x,a.y+b.y);
}
pointt operator - (point a,point b)
{
return point(a.x-b.x,a.y-b.y);
}
int dcmp(double x)
{
if(fabs(x)<eps) return ;
else return x<?-:;
}
bool operator == (const point &a,const point &b)
{
return dcmp(a.x-b.x)==&&dcmp(a.y-b.y)==;
}
double cross(point a,point b)
{
return a.x*b.y-a.y*b.x;
}
double Polyarea(point p[],int n)
{
if(n<) return ;
double area = ;
for(int i = ; i < n ; i++)
area+=cross(p[i],p[i+]);
return fabs(area)/;
}
//double Polyarea(point p[], int n)
//{
// if(n < 3) return 0.0;
// double s = p[0].y * (p[n - 1].x - p[1].x);
// p[n] = p[0];
// for(int i = 1; i < n; ++ i)
// s += p[i].y * (p[i - 1].x - p[i + 1].x);
// return fabs(s * 0.5);
//}
bool intersection1(point p1, point p2, point p3, point p4, point& p) // 直线相交
{
double a1, b1, c1, a2, b2, c2, d;
a1 = p1.y - p2.y;
b1 = p2.x - p1.x;
c1 = p1.x*p2.y - p2.x*p1.y;
a2 = p3.y - p4.y;
b2 = p4.x - p3.x;
c2 = p3.x*p4.y - p4.x*p3.y;
d = a1*b2 - a2*b1;
if (!dcmp(d)) return false;
p.x = (-c1*b2 + c2*b1) / d;
p.y = (-a1*c2 + a2*c1) / d;
return true;
} double convexpolygon(point p[],point q[],int n,int m)
{
int i,j;
point ch[],cnt[];
p[n] = p[],q[m] = q[];
memcpy(ch,q,sizeof(point)*(m+));
int f2,g = ;
for(i = ;i < n; i++)
{
int f1 = dcmp(cross(p[i+]-p[i],ch[]-p[i]));
g = ;
for(j = ;j < m; j++,f1 = f2)
{
if(f1>=) cnt[g++] = ch[j];
f2 = dcmp(cross(p[i+]-p[i],ch[j+]-p[i]));
if((f1^f2)==-)
{
point pp;
intersection1(p[i],p[i+],ch[j],ch[j+],pp);
cnt[g++] = pp;
}
}
cnt[g] = cnt[];
memcpy(ch,cnt,sizeof(point)*(g+));
m = g;
}
return Polyarea(ch,g);
}
double solve(point p[],point q[],int n,int m)
{
int i,j;
double area = ;
point tp[],tq[];
tp[] = p[];tq[] = q[];
for(i = ;i < n-; i++)
{
int k1 = dcmp(cross(p[i]-p[],p[i+]-p[]));
tp[] = p[i],tp[] = p[i+];
if(k1 < ) swap(tp[],tp[]); for(j = ;j < m- ;j++)
{
tq[] = q[j],tq[] = q[j+];
int k2 = dcmp(cross(q[j]-q[],q[j+]-q[]));
if(k2<) swap(tq[],tq[]); area+=convexpolygon(tp,tq,,)*k1*k2;
}
}
return Polyarea(p,n)+Polyarea(q,m)-area;
}
int main()
{
int n,m,i;
while(scanf("%d%d",&n,&m)!=EOF)
{
for(i = ; i < n ;i++)
{
scanf("%lf%lf",&p[i].x,&p[i].y);
}
for(i = ; i < m; i++)
{
scanf("%lf%lf",&q[i].x,&q[i].y);
}
p[n] = p[],q[m] = q[];
double ans = solve(p,q,n,m);
printf("%.2f\n",ans);
}
return ;
}
上一篇:删除每列(和对应行)的异常值


下一篇:WebClient, HttpClient, HttpWebRequest ,RestSharp之间的区别与抉择