BZOJ2618[Cqoi2006]凸多边形——半平面交

灰太狼 2022-01-13 04:13 272阅读 0赞

## 题目描述 ##

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

![1_287_29.jpg][]

则相交部分的面积为5.233。

## 输入 ##

第一行有一个整数*n*，表示凸多边形的个数，以下依次描述各个多边形。第i个多边形的第一行包含一个整数*mi*，表示多边形的边数，以下*mi*行每行两个整数，逆时针给出各个顶点的坐标。

## 输出 ##

输出文件仅包含一个实数，表示相交部分的面积，保留三位小数。

## 样例输入 ##

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

## 提示 ##

100%的数据满足：2<=*n*<=10，3<=*mi*<=50，每维坐标为\[-1000,1000\]内的整数

半平面交模板题，就是求多边形所有边的半平面交。

#include<set>
    #include<map>
    #include<queue>
    #include<stack>
    #include<cmath>
    #include<cstdio>
    #include<vector>
    #include<bitset>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    const double eps=1e-5;
    struct lty
    {
    	double x,y;
    	lty(double X=0,double Y=0){x=X,y=Y;}
    };
    struct miku
    {
    	double x,y;
    	miku(double X=0,double Y=0){x=X,y=Y;}
    };
    struct line
    {
    	lty s,t;
    	line(){}
    	line(lty S,lty T){s=S,t=T;}
    };
    miku operator -(lty a,lty b)
    {
    	return miku(a.x-b.x,a.y-b.y);
    }
    miku operator *(miku a,double b)
    {
    	return miku(a.x*b,a.y*b);
    }
    lty operator +(lty a,miku b)
    {
    	return lty(a.x+b.x,a.y+b.y);
    }
    double get(miku a,miku b)
    {
    	return a.x*b.y-a.y*b.x;
    }
    double tan(miku a)
    {
    	return atan2(a.y,a.x);
    }
    double tan(line a)
    {
    	miku res=a.t-a.s;
    	return atan2(res.y,res.x);
    }
    int n,m,k;
    int cnt;
    line a[100010];
    line q[100010];
    lty p[100010];
    int D(double x)
    {
    	if(fabs(x)<eps)
    	{
    		return 0;
    	}
    	return x<0?-1:1;
    }
    double ask(int num)
    {
    	double ans=0;
    	for(int i=2;i<num;i++)
    	{
    		ans+=fabs(get(p[i]-p[1],p[i+1]-p[1]));
    	}
    	return ans/2.0;
    }
    bool cmp(line a,line b)
    {
    	miku v1=a.t-a.s,v2=b.t-b.s;
    	double s1=tan(v1),s2=tan(v2);
    	int d=D(s1-s2);
    	if(!d)
    	{
    		return get(v1,b.t-a.s)>0;
    	}
    	return d<0;
    }
    lty find(line a,line b)
    {
    	miku u=a.s-b.s,v=a.t-a.s,w=b.t-b.s;
    	if(!D(get(v,w)))
    	{
    		return a.s;
    	}
    	double x=get(w,u)/get(v,w);
    	return a.s+v*x;
    }
    bool check(line a,line b,line c)
    {
    	lty e=find(b,c);
    	int d=D(get(a.t-a.s,e-a.s));
    	return d>0?false:true;
    }
    void solve()
    {
    	sort(a+1,a+n+1,cmp);
    	int l=1,r=0;
    	int cnt=0;
    	for(int i=1;i<n;i++)
    	{
    		if(!D(tan(a[i])-tan(a[i+1])))
    		{
    			continue;
    		}
    		a[++cnt]=a[i];
    	}
    	a[++cnt]=a[n];
    	for(int i=1;i<=cnt;i++)
    	{
    		while(l<r&&check(a[i],q[r],q[r-1]))
    		{
    			r--;
    		}
    		while(l<r&&check(a[i],q[l],q[l+1]))
    		{
    			l++;
    		}
    		q[++r]=a[i];
    	}
    	while(l<r&&check(q[l],q[r],q[r-1]))
    	{
    		r--;
    	}
    	while(l<r&&check(q[r],q[l],q[l+1]))
    	{
    		l++;
    	}
    	int num=0;
    	for(int i=l;i<r;i++)
    	{
    		p[++num]=find(q[i],q[i+1]);
    	}
    	p[++num]=find(q[r],q[l]);
    	if(num<3)
    	{
    		printf("0.000");
    		return ;
    	}
    	printf("%.3f",ask(num));
    }
    int main()
    {
    	scanf("%d",&k);
    	while(k--)
    	{
    		scanf("%d",&m);
    		for(int i=1;i<=m;i++)
    		{
    			cnt++;
    			if(i!=1)
    			{
    				a[cnt].s=a[cnt-1].t;
    			}
    			scanf("%lf%lf",&a[cnt].t.x,&a[cnt].t.y);
    		}
    		a[cnt-m+1].s=a[cnt].t;
    	}
    	n=cnt;
    	solve();
    }

转载于:https://www.cnblogs.com/Khada-Jhin/p/10632621.html

[1_287_29.jpg]: https://lydsy.com/JudgeOnline/upload/201203/1%287%29.jpg