【CQOI2006】凸多边形计算几何

2019-11-06 06:55:28

字体：大中小

来源：转载

供稿：网友

题目描述

　　逆时针给出n个凸多边形的顶点坐标，求它们交的面积。例如n=2时，两个凸多边形如下图： 2333 　　则相交部分的面积为5.233。

数据范围

2<=n<=10，3<=mi<=50，每维坐标为[-1000,1000]内的整数

样例输入

2 6 -2 0 -1 -2 1 -2 2 0 1 2 -1 2 4 0 -3 1 -1 2 2 -1 0

样例输出

5.233

解题思路

半平面交，用每一条边去割原来的图形

代码

#include <algorithm>#include <iostream>#include <cstring>#include <cstdlib>#include <cstdio>#include <cmath>#include <ctime>#define Maxn 55using namespace std;struct Point{ double x,y;}a[Maxn],b[Maxn],c[Maxn];int m,n,nn;void Init(){ scanf("%d%d",&m,&n); for(int i=1;i<=n;i++) scanf("%lf%lf",&a[i].x,&a[i].y);}double Cross(Point a,Point b,Point c){ return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);}void AddCross(Point a,Point b,Point C,Point d){ double c1=Cross(a,d,b),c2=Cross(a,C,b); c[++nn]=(Point){(c1*C.x-c2*d.x)/(c1-c2),(c1*C.y-c2*d.y)/(c1-c2)};}void Cut(Point A,Point B){ nn=0; a[n+1]=a[1]; for(int i=1;i<=n;i++){ if(Cross(a[i],B,A)<=0){ c[++nn]=a[i]; if(Cross(a[i+1],B,A)>0)AddCross(A,B,a[i+1],a[i]); }else if(Cross(a[i+1],B,A)<0)AddCross(A,B,a[i+1],a[i]); } for(int i=1;i<=nn;i++)a[i]=c[i]; n=nn;}int main(){ Init(); while(m---1){//233 int t; scanf("%d",&t); for(int i=1;i<=t;i++) scanf("%lf%lf",&b[i].x,&b[i].y); b[t+1]=b[1]; for(int i=1;i<=t;i++) Cut(b[i],b[i+1]); } double Ans=0; a[n+1]=a[1]; for(int i=1;i<=n;i++) Ans+=a[i].x*a[i+1].y-a[i].y*a[i+1].x; PRintf("%.3lf",fabs(Ans)/2);}

上一篇：activiti工作流的web流程设计器整合视频教程 SSM和独立部署

下一篇：51Nod 算法马拉松22 代码能力捉急记