P3829 [SHOI2012] 信用卡凸包 题解

本文主要是介绍P3829 [SHOI2012] 信用卡凸包 题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

解题思路

不难的题，但是细节有亿点多……

观察三组样例不难发现，我们可以把所有的信用卡的圆角去掉，变成一个长 $b-2\cdot r$，宽 $a-2\cdot r$ 的矩形。考虑将这个矩形的四个顶点加入一个点集中，然后求凸包，答案即为这个凸包的周长加上一个半径为 $r$ 的 ⚪ 的周长。

那么怎么求出凸包周长呢？显然的，我们在求出所有点的坐标后跑一遍 Andrew 或者 Graham 即可。那么现在问题变为如何求出所有点的坐标。

因为题目中已经给出了每张信用卡中心的坐标，那么我们可以很轻松地得到每张信用卡旋转前矩形四个顶点的坐标（其实就是四分之一圆的圆心），那么现在来解决旋转的问题。

我们分别对于每张信用卡进行考虑。我们不妨将中心移到单位圆的圆心上，那么我们根据顶点到中心的 $x$、$y$ 坐标之差（注意一定是按照顶点减中心的顺序），通过 atan2 函数就可以方便的算出当前顶点移动后与 $x$ 轴的夹角大小。那么旋转就相当于是给夹角加上了一个度数，我们加上这个度数后直接用 $\sin$ 和 $\cos$ 的值计算新得到的顶点坐标即可。

注意事项

• atan2 函数使用时应该把 $y$ 放前面，$x$ 放后面；
• 对于所有点按极角排序后一定要去重，不然一个点可能被多次计算；
• 判断两个点是否相等时要加入精度限制，不然去重等于没去；
• $\pi$ 的值尽量取大一点，不然误差还是挺大的，尤其在乘以一个大的 $r$ 后。

AC 代码

似乎有点长？

#include<math.h>
#include<stdio.h>
#include<valarray>
#include<stdlib.h>
#include<algorithm>
#define eps 1e-9
#define N 40005
struct Point{double x,y;//向量初始化Point():x(0),y(0){}Point(double a,double b):x(a),y(b){}//向量加inline Point operator +(const Point &b) const {return (Point){x+b.x,y+b.y};}//向量减inline Point operator -(const Point &b) const {return (Point){x-b.x,y-b.y};}//向量乘一个数inline Point operator *(const double &b) const {return (Point){x*b,y*b};}//向量除一个数inline Point operator /(const double &b) const {return (Point){x/b,y/b};}//向量点乘inline double operator ^(const Point &b) const {return x*b.x+y*b.y;}//向量叉乘inline double operator *(const Point &b) const {return x*b.y-y*b.x;}inline bool operator ==(const Point &b) const {bool _1=fabs(x-b.x)<eps;bool _2=fabs(y-b.y)<eps;return _1&&_2;}
}a[N],sta[N];
inline double dis(double x1,double y1,double x2,double y2
){  double Ox=(x1-x2)*(x1-x2);double Oy=(y1-y2)*(y1-y2);return(double)sqrt(Ox+Oy);
}
inline double dis(const Point &A,const Point &B
){double x1=A.x,y1=A.y;double x2=B.x,y2=B.y;return dis(x1,y1,x2,y2);
}
inline bool cmp(Point A,Point B
){Point _1=A-a[1];Point _2=B-a[1];double d=_1*_2;if(d>0) return true;double d1=dis(a[0],A);double d2=dis(a[0],B);if(d==0&&d1<d2) return true;return false;
}
int m,n,tail;
double A,B,R;
double x,y,d;
inline void Revolve(double &NowX,double &NowY,const double &CentreX,const double &CentreY,const double &Angle
){double r=dis(NowX,NowY,CentreX,CentreY);double DeltaX=NowX-CentreX;double DeltaY=NowY-CentreY;double NowAngle=atan2(DeltaY,DeltaX);NowAngle+=Angle;double NowSin=sin(NowAngle);double NowCos=cos(NowAngle);NowX=CentreX+(r*NowCos);NowY=CentreY+(r*NowSin);
}
inline void Turn(const double &x,const double &y,const double &d
){double x1,x2,x3,x4;double y1,y2,y3,y4;x1=x+B*0.5-R,y1=y+A*0.5-R;x2=x-B*0.5+R,y2=y+A*0.5-R;x3=x-B*0.5+R,y3=y-A*0.5+R;x4=x+B*0.5-R,y4=y-A*0.5+R;Revolve(x1,y1,x,y,d);Revolve(x2,y2,x,y,d);Revolve(x3,y3,x,y,d);Revolve(x4,y4,x,y,d);a[++n]={x1,y1},a[++n]={x2,y2};a[++n]={x3,y3},a[++n]={x4,y4};
}
inline void init(){scanf("%d",&m);scanf("%lf",&A);scanf("%lf",&B);scanf("%lf",&R);for(int i=1;i<=m;++i){scanf("%lf",&x);scanf("%lf",&y);scanf("%lf",&d);Turn(x,y,d);}for(int i=2;i<=n;++i){if(a[i].y>a[1].y)continue;if(a[i].y==a[1].y&&a[i].x>=a[1].x)continue;std::swap(a[1],a[i]);}std::sort(a+2,a+1+n,cmp);n=std::unique(a+1,a+n+1)-a-1;tail=1;sta[tail]=a[1];
}
double C,ans;
inline void Andrew(){for(int i=2;i<=n;++i){while(tail>1){Point d1=sta[tail]-sta[tail-1];Point d2=a[i]-sta[tail];if((d1*d2)>=0) break;--tail;}sta[++tail]=a[i];}sta[++tail]=a[1];for(int i=1;i<tail;++i)C+=dis(sta[i],sta[i+1]);
}
const double Pi=3.1415926535898;
signed main(){init();Andrew();ans=C+(2.0*R*Pi);printf("%.2lf",ans);
}

这篇关于P3829 [SHOI2012] 信用卡凸包 题解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---