模板题
题意:给定两个凸多边形,求出合并后的面积,这个合并后的面积不包括重叠部分。
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<algorithm>
using namespace std;
const int maxn = 155;
const int maxm = 155;
const double eps = 1e-8;
const double pi = acos(-1.0);
struct Point{
double x,y;
};
struct Line{
Point a,b;
};
Point pnt1[ maxn ],res[ maxm ],pnt2[ maxn ],tp[ maxm ];
double xmult( Point op,Point sp,Point ep ){
return (sp.x-op.x)*(ep.y-op.y)-(sp.y-op.y)*(ep.x-op.x);
}
double dist( Point a,Point b ){
return sqrt( (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y) );
}
void Get_equation( Point p1,Point p2,double &a,double &b,double &c ){
a = p2.y-p1.y;
b = p1.x-p2.x;
c = p2.x*p1.y-p1.x*p2.y;
}//直线方程
Point Intersection( Point p1,Point p2,double a,double b,double c ){
double u = fabs( a*p1.x+b*p1.y+c );
double v = fabs( a*p2.x+b*p2.y+c );
Point tt;
tt.x = (p1.x*v+p2.x*u)/(u+v);
tt.y = (p1.y*v+p2.y*u)/(u+v);
return tt;
}//交点、按照三角比例求出交点
double GetArea( Point p[],int n ){
double sum = 0;
for( int i=2;i<n;i++ ){
sum += xmult( p[1],p[i],p[i+1] );
}
return -sum/2.0;
}//面积,顺时针为正
void cut( double a,double b,double c,int &cnt ){
int temp = 0;
for( int i=1;i<=cnt;i++ ){
if( a*res[i].x+b*res[i].y+c>-eps ){//>=0
tp[ ++temp ] = res[i];
}
else{
if( a*res[i-1].x+b*res[i-1].y+c>eps ){
tp[ ++temp ] = Intersection( res[i-1],res[i],a,b,c );
}
if( a*res[i+1].x+b*res[i+1].y+c>eps ){
tp[ ++temp ] = Intersection( res[i],res[i+1],a,b,c );
}
}
}
for( int i=1;i<=temp;i++ )
res[i] = tp[i];
res[ 0 ] = res[ temp ];
res[ temp+1 ] = res[ 1 ];
cnt = temp;
}
int main(){
int m,n;
while( scanf("%d",&n)==1,n ){
for( int i=1;i<=n;i++ ){
scanf("%lf%lf",&pnt1[i].x,&pnt1[i].y);
}
scanf("%d",&m);
for( int i=1;i<=m;i++ ){
scanf("%lf%lf",&pnt2[i].x,&pnt2[i].y);
}
double sumArea1,sumArea2,Area;
sumArea1 = GetArea( pnt1,n );
sumArea2 = GetArea( pnt2,m );
if( sumArea1<eps ){
reverse( pnt1+1,pnt1+1+n );
}
pnt1[ 0 ] = pnt1[ n ];
pnt1[ n+1 ] = pnt1[ 1 ];
if( sumArea2<eps ){
reverse( pnt2+1,pnt2+1+m );
}
pnt2[ 0 ] = pnt2[ m ];
pnt2[ m+1 ] = pnt2[ 1 ];
for( int i=0;i<=n+1;i++ ){
res[i] = pnt1[i];
}
int cnt = n;
for( int i=1;i<=m;i++ ){
double a,b,c;
Get_equation( pnt2[i],pnt2[i+1],a,b,c );
cut(a,b,c,cnt);
}
Area = GetArea( res,cnt );
double ans = fabs(sumArea1)+fabs(sumArea2)-2.0*fabs(Area);
printf("%8.2lf",ans);
}
puts("");
return 0;
}
分享到:
相关推荐
300+ AC 代码 。 大数 , 线段树 , 字符串 , dp.....
2、new做两件事,一是分配内存,二是调用类的构造函数 3、new建立的是一个对象,而malloc分配的是一块内存 4、new/delete是保留字,不需要头文
本人准备2020年保研机试时刷的题目(虽然最后机试取消了,...来自某中流985,在HDU和vjudge平台上大概刷了400道。本文件地图(excel表格)包含了绝大部分我刷过的题目,笔记中具有思路、代码、总结和心得。 大佬勿入!
ACM题库,一些题目和答案,以及解题报告,传上来共享
杭电OnlineJudge 200-2099的解题报告
acm入门训练和日常训练 对于初学者以及acm爱好者有叫大帮助
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
hdu 1695 GCD(欧拉函数+容斥原理).docx
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu2101AC代码
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
acm hdu as easy as a+b