BZOJ2829 FJWC 2015 信用卡凸包 【凸包+坐标变换】
[FJWC2015]信用卡凸包
时间限制:1000MS
内存限制:131072KB
Description
信用卡是一个矩形,唯四个角作了圆滑处理,使它们都与矩形四边相切的1/4圆,如下图所示。现在平面上有一些规格相同的信用卡,试求其凸包的周长。注意凸包未必是多边形,因为它可能包含若干段圆弧(具体例子请看样例)。
Input Format
输入的第一行是一个正整数n,表示信用卡的张数。
第二行包含三个实数a, b,r,分别表示信用卡(圆滑处理前)竖直方向的长度、水平方向的长度,以及1/4圆的半径。
之后n行,每行包含三个实数x, y, θ,分别表示一张信用卡中心(即对角线交点)的横、纵坐标,以及绕中心逆时针旋转的弧度。
Output Format
输出只有一行,包含一个实数,表示凸包的周长,四舍五入精确到小数点后2位。
Sample Input & Output:略
Hint
【样例1 说明】
本样例中的2张信用卡的轮廓在上图中用实线标出,如果视1.5707963268为pi/2,则其凸包的周长为16+4sqrt(2)。
【样例2说明】
本样例中的3张信用卡的轮廓在下图中用实线标出。
【样例3说明】
本样例中的3张信用卡的轮廓在下图中用实线标出。
【数据规模】
对于100%的数据,有0.1 ≤ a, b≤ 1000000.0,以及0.0 ≤ r< min{a/4, b/4},n≤100000
对所有的信用卡,有|x|, |y| ≤ 1000000.0,以及0 ≤ θ< 2π。
对于50%的数据,n≤2。:-)
对于70%的数据,n≤100。
其中两组数据r=0。
另外其中三组数据θ=0.
另外还有一组数据r=θ=0.
【题解】
我们发现,要直接求信用卡凸包比较复杂。
我们会发现,只需要求圆心的凸包即可,然后最后答案加上$2πr$就行了。
于是就直接做啦~
感谢97小叶子11和n+e的指导。
# include <stdio.h> # include <algorithm> # include <math.h> # include <vector> using namespace std; int d[4][2] = {1, 1, 1, -1, -1, 1, -1, -1}; const double eps=1e-7,pi=acos(-1.0); inline double abs(double a) { return a<0?-a:a; } inline double add(double a,double b) { if (abs(a+b)<eps*(abs(a)+abs(b)))return 0; return a+b; } struct P { double x,y; P () {} P (double x,double y):x(x),y(y){} P operator + (P a) { return P(add(x,a.x),add(y,a.y)); } P operator - (P a) { return P(add(x,-a.x),add(y,-a.y)); } P operator * (double d) { return P(x*d,y*d); } double dot(P a) { return add(x*a.x,y*a.y); } double det(P a) { return add(x*a.y,-y*a.x); } }; P rotate(P a,double rot) { return P(a.x*cos(rot)-a.y*sin(rot),a.x*sin(rot)+a.y*cos(rot)); } inline int cmp_x(P a, P b) { return a.x<b.x||(a.x==b.x&&a.y<b.y); } inline vector<P> convexhull(vector<P>ps) { int n=ps.size(),k=0; sort(ps.begin(),ps.end(),cmp_x); vector<P> qs(n*2); for (int i=0;i<n;++i) { while(k>1&&(qs[k-1]-qs[k-2]).det(ps[i]-qs[k-1])<=0)--k; qs[k++]=ps[i]; } for (int i=n-2,t=k;i>=0;--i) { while(k>t&&(qs[k-1]-qs[k-2]).det(ps[i]-qs[k-1])<=0)--k; qs[k++]=ps[i]; } qs.resize(k-1); return qs; } int N;double A,B,r,z,ans; inline double dis(P a,P b) { return sqrt((a-b).dot(a-b)); } int main() { vector<P>ps; scanf("%d",&N); scanf("%lf%lf%lf",&A,&B,&r);A=A/2-r,B=B/2-r; for(int i=1;i<=N;++i) { P b; scanf("%lf%lf%lf",&b.x,&b.y,&z); P t; for (int j=0;j<4;++j) { t=rotate(P(d[j][0]*B,d[j][1]*A),z)+b; ps.push_back(t); } } vector<P>qs=convexhull(ps); int s=qs.size();ans=0.0; for (int i=0;i<s-1;++i) ans+=dis(qs[i],qs[i+1]); ans+=dis(qs[s-1],qs[0]); ans+=2*pi*r; printf("%.2lf\n",ans); return 0; }