Acwing 2935：信用卡凸包（计算几何问题转化 + 凸包）

短命女 2022-11-06 14:00 215阅读 0赞

### 原题链接 ###

传送门：[Acwing 2935：信用卡凸包][Acwing 2935]

### 题目大意 ###

给n张信用卡，每张大小都一样，然后给每张卡的四角进行圆滑处理，即割一个 1 4 \\frac 1 4 41圆。然后将n张卡放在平面上，求这n张卡的凸包，如下图所示：  
![eg][]  
输入信用卡的长宽和小圆半径，然后输出n张卡中心的坐标以及旋转的角度。求凸包周长。

### 思路 ###

这道题一看是[凸包][Link 1]，但又不太一样，这里的每个点都不是一个点，而是一个圆弧，这就没法直接用凸包算了。所以我们就得向普通凸包转化，我们就看一下这个信用卡凸包的几何特征！如图：  
![eg][eg 1]

注意这里的圆弧都不一定是等长的。我们将所有的切线延长，两两相交于一点，构成了一个凸多边形，他们有个偏转角 θ \\theta θ，而这个偏转角就是这个凸多边形的外角，所以所有的偏转角之和就是凸多边形的外角和是360°，而因为圆的弦切角定理可知，这个外角就是圆弧所对的圆心角，因此我们就可以得出所有圆弧的总长度就是一个圆的周长。  
这个凸包是有圆弧部分和直线部分组成，然后我们看看直线部分长度怎么算。如图：  
![eg][eg 2]  
在蓝色阴影面积内，有两个直角（切线和切点的半径垂直），且有两个等边（两短边都是半径长度），所以这个是一个矩形，因此外面的直线长度就可以转化成里面的直线长度，而里面的蓝色线又是所有圆心的凸包。因此就将原问题转化成了求圆心的凸包再加个圆周长即可。

### 代码详解 ###

#include<iostream>
    #include<cmath>
    #include<algorithm>
    using namespace std;
    const int N = 40010;
    const double PI = acos(-1);	//自定义pi
    typedef pair<double,double> PDD;	//用pair来存点
    
    int n,cnt,top,stk[N];	//手动开栈
    PDD p[N];	//p存所有圆心的点坐标
    bool used[N];		//used是判断点是否被用作边界
    int dx[4] = { 1,1,-1,-1},dy[4] = { 1,-1,-1,1};	//从中心向四个方向偏移得到圆心
    
    double lens(PDD a,PDD b)	//求两点距离
    { 
    	double x = a.first - b.first;
    	double y = a.second - b.second;
    	return sqrt(x*x + y*y);		//距离 = 坐标差的平方和开根号
    }
    
    PDD rotate(PDD a,double b)	//求向量a旋转b角度后的向量
    { 
    	return { a.first*cos(b) + a.second*sin(b) ,-a.first*sin(b) + a.second*cos(b)};	//在基础知识中有
    }
    
    double cross(PDD a,PDD b,PDD c)		//求ab向量和ac向量叉积
    { 
    	PDD u,v;
    	u = { b.first-a.first,b.second-a.second};	//先算出两向量
    	v = { c.first-a.first,c.second-a.second};
    	return u.first*v.second - v.first*u.second;	//x1*y2 - x2*y1
    }
    
    double andrew()		//andrew求凸包算法
    { 
    	sort(p,p+cnt);	//先对点排序，用pair存点方便排序
    	for(int i = 0;i < cnt;i++)	//从左往右维护每个点，这里总点数是cnt不是n！
    	{ 
    		while(top >= 2 && cross(p[stk[top-1]],p[stk[top]],p[i]) > 0)	//如果栈里元素大于等于2且叉积大于0
    		{ 
    			used[stk[top]] = 0;	//就出栈，同时取消使用标记
    			top--;		//出栈
    		}
    		stk[++top] = i;		//新点入栈
    		used[i] = 1;		//标记使用
    	}
    	used[0] = 0;		//将出发点取消标记，因为一会还要再算一遍出发点
    	for(int i = cnt-2;i >= 0;i--)
    	{ 
    		while(top >= 2 && cross(p[stk[top-1]],p[stk[top]],p[i]) > 0)
    			top--;
    		stk[++top] = i;
    	}
    
    	double perimeter = 0;		//周长
    	for(int i = 2;i <= top;i++)	//边界上的每两点间距离加和就是周长，注意这里栈是从下标1开始存的
    		perimeter += lens(p[stk[i-1]],p[stk[i]]);
    	return perimeter;	//返回周长
    }
    
    int main()
    { 
    	double a,b,r;
    	cin >> n;
    	cin >> a >> b >> r;
    	a = a/2-r,b = b/2-r;	//对a和b预处理，从中心点加上b/2再减去半径r才是横坐标，画个图理解一下
    	while(n--)
    	{ 
    		double x,y,z;
    		cin >> x >> y >> z;
    		for(int i = 0;i < 4;i++)	//从中心点向四个方向求圆心
    		{ 
    			PDD t = rotate({ dx[i]*b,dy[i]*a},-z);	//先旋转向量
    			p[cnt++] = { t.first+x,t.second+y};	//在加上中心点坐标
    		}
    	}
    	
    	double ans = 0;
    	ans = andrew();
    	printf("%.2lf\n",ans + 2*PI*r);		//直线周长加上圆的周长就是原凸包周长
    
    	return 0;
    }

与向量有关的[基础知识可以看这里][Link 2]

[Acwing 2935]: https://www.acwing.com/problem/content/2938/
[eg]: /images/20221023/49ed89a1aca74aa791cbceb09848d174.png
[Link 1]: https://blog.csdn.net/qq_45735851/article/details/114553142
[eg 1]: /images/20221023/53e0f10d46474d45bb0988af6a251ac3.png
[eg 2]: /images/20221023/3d61067315624431b746a805579de2c8.png
[Link 2]: https://blog.csdn.net/qq_45735851/article/details/114382634