Bzoj2829 信用卡凸包

Time Limit: 10 Sec Memory Limit: 128 MBSec Special Judge
Submit: 333 Solved: 155

Description

Input

Output

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

本样例中的2张信用卡的轮廓在上图中用实线标出，如果视1.5707963268为

Pi/2(pi为圆周率),则其凸包的周长为16+4*sqrt(2)

Source

几何凸包

把矩形边长减去圆的直径，得到有效边长。计算出每个矩形的四个点，找到凸包，再加上一个圆的周长就是答案。

迷之WA，注释掉的旋转方法不知为何不对（小样例居然都过了）

 /*by SilverN*/

 #include<algorithm>

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 #include<vector>

 using namespace std;

 const double Pi=acos(-1.0);

 const int mxn=;

 struct point{

     double x,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[mxn];

 double cross(point a,point b){return a.x*b.y-a.y*b.x;}

 double dist(point a,point b){return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);}

 int cmp(point a,point b){

     double tmp=cross(a-p[],b-p[]);

     return (tmp< || (tmp== && dist(a,p[])>dist(b,p[])));

 }

 int cmp2(point a,point b,point p){

     double tmp=cross(a-p,b-p);

     return (tmp< || (tmp== && dist(a,p)>=dist(b,p)));

 }

 point rotate(point a,double angle){

     return (point){a.x*cos(angle)-a.y*sin(angle),a.x*sin(angle)+a.y*cos(angle)};

 }

 point move(point a,double len,double an){

     return (point){a.x+len*cos(an),a.y+len*sin(an)};

 }

 int n;

 double a,b,r;

 double x,y,th;

 int st[mxn],top;

 int main(){

     int i,j;

     scanf("%d",&n);

     scanf("%lf%lf%lf",&a,&b,&r);

     a-=*r;b-=*r;

     top=;

     for(i=;i<=n;i++){

         scanf("%lf%lf%lf",&x,&y,&th);

         for(j=;j<=;j++)

         {

             point tmp=move((point){x,y},b/,th+Pi*(j-)/);

             p[++top]=move(tmp,a/,th+Pi*j/);

             swap(a,b);

         }

 //        point tmp;

 /*

         tmp.x=a/2;tmp.y=b/2;p[++top]=(point){x,y}+rotate(tmp,th);

         tmp.x=-a/2;tmp.y=b/2;p[++top]=(point){x,y}+rotate(tmp,th);

         tmp.x=a/2;tmp.y=-b/2;p[++top]=(point){x,y}+rotate(tmp,th);

         tmp.x=-a/2;tmp.y=-b/2;p[++top]=(point){x,y}+rotate(tmp,th);

 */

     }

     n=top;top=;

     int s=;

     for(i=;i<=n;i++){

         if(p[i].x<p[s].x || (p[i].x==p[s].x && p[i].y<p[s].y))s=i;

     }

     swap(p[s],p[]);

     sort(p+,p+n+,cmp);

     p[n+]=p[];

     n++;

     for(i=;i<=n;i++){

         while(top> && cmp2(p[i],p[st[top]],p[st[top-]]))top--;

         st[++top]=i;

     }

     double ans=;

     ans+=Pi**r;

     for(i=;i<top;i++){

         ans+=sqrt(dist(p[st[i]],p[st[i+]]));

     }

     printf("%.2lf\n",ans);

     return ;

 }

 /*

 5

 12.0 6.0 2.0

 0.0 0.0 0.0

 1 1 1

 2 2 1.5707963268

 1 7 0

 2.0 -2.0 1.5707963268

 */

巴特西