bzoj2829 信用卡凸包 [凸包]

in 题目 with 0 comment

Description

信用卡是一个矩形,唯有四个角做了圆滑处理,使他们都是与矩形的两边相切的1/4圆,入校图所示.现在平面上有一些规格相同的信用卡,试求其凸包的周长.注意凸包未必是多边形,因为他们可能包含若干段圆弧
110.jpg


Input

输入第一行是一个正整数n,表示信用卡的张数.
第二行包含三个实数a,b,r,分别表示信用卡(圆滑处理前)竖直方向的长度,宽度以及1/4圆的半径.
之后n行,每行包含三个实数x,y,$\theta$,分别表示一张信用卡中心(即对角线交点)的横,纵坐标,以及绕中心逆时针旋转的弧度.


Output

输入只有一行,包含一个史书,表示凸包的周长,四舍五入精确到小数点后2位


Sample Input

2
6.0 2.0 0.0
0.0 0.0 0.0
2.0 -2.0 1.5707963268


Sample Output

21.66


HINT

44(6).jpg
本样例中的2张信用卡的轮廓在上图中用实线标出,如果视1.5707963268为Pi/2(pi为圆周率),则其凸包的周长为16+4*sqrt(2)


Solution

基本上是凸包模板题,我们可以先求出每个信用卡四个圆形位置,对这些点求凸包,然后加上一个圆的周长即可.
正确性:
IMG_0290(20170327-204835).jpg
但凸包一直写跪TAT,还我时间QAQ,求凸包一定要注意对边界条件的处理.


Code

#include<bits/stdc++.h>
#define maxn 100010
//#define DEBUG
using namespace std;
int n,cnt=0;
double a,b,r,ans=0;
const double pi=acos(-1.0);
const double eps=1e-8;

int dcmp(double x)
{
    if(fabs(x)<eps) return 0;
    else return x<0?-1:1;
}

struct square
{
    double x,y,angle;
}s[maxn];

struct Point
{
    double x,y;
    Point(double x=0,double y=0):x(x),y(y){}
    Point operator + (Point rhs) { return Point(x+rhs.x,y+rhs.y); }
    Point operator - (Point rhs) { return Point(x-rhs.x,y-rhs.y); }
}p[4*maxn],con[4*maxn];

typedef Point Vector;

bool operator ==(const Vector& a,const Vector& b) 
{ 
    return dcmp(a.x-b.x)==0 && dcmp(a.y-b.y)==0; 
}
bool operator < (Point a,Point b) 
{ 
    return dcmp(a.x-b.x)<0 || (dcmp(a.x-b.x)==0 && dcmp(a.y-b.y)<0 ); 
}

double dis2(Point a) { return a.x*a.x+a.y*a.y; }

Point rotate(Point p,double x,double rad)
{
    return Point(p.x+x*cos(rad),p.y+x*sin(rad));
}
double cross(Vector a,Vector b)
{
    return dcmp(a.x*b.y-a.y*b.x);
}

void build()
{
    for(int i=0;i<n;++i)
        for(int j=0;j<4;++j)
        {
            Point t=rotate(Point(s[i].x,s[i].y),b/2,s[i].angle+j*pi/2);
            p[cnt++]=rotate(t,a/2,s[i].angle+(j+1)*pi/2);
            swap(a,b);
        }
}

void convexhall()
{
    sort(p,p+cnt);
    cnt=unique(p,p+cnt)-p;
#ifdef DEBUG
    for(int i=0;i<cnt;++i)
        printf("p[%d]=(%.2lf,%.2lf)\n",i,p[i].x,p[i].y);
#endif
    int num=0;
    for(int i=0;i<cnt;++i)
    {
        while(num>1 && cross(con[num-1]-con[num-2],p[i]-con[num-2])<=0) num--;
        con[num++]=p[i];
    }
    int k=num;
    for(int i=cnt-2;i>=0;--i)
    {
        while(num>k && cross(con[num-1]-con[num-2],p[i]-con[num-2])<=0) num--;
        con[num++]=p[i];
    }
    cnt=num-1;
#ifdef DEBUG
    for(int i=0;i<cnt;++i)
        printf("con[%d]=(%.2lf,%.2lf)\n",i,con[i].x,con[i].y);
#endif
    return;
}

void solve()
{
    for(int i=1;i<cnt;++i)
        ans+=sqrt(dis2(con[i]-con[i-1]));
    ans+=sqrt(dis2(con[cnt-1]-con[0]));
    printf("%.2lf\n",ans);
}

int main()
{
    scanf("%d",&n);
    scanf("%lf%lf%lf",&a,&b,&r);
    a-=2*r,b-=2*r,ans+=2*pi*r;
    for(int i=0;i<n;++i) scanf("%lf%lf%lf",&s[i].x,&s[i].y,&s[i].angle);
    build();
    convexhall();
    solve();
    return 0;
} 

扫描二维码,在手机上阅读!
Responses