【bzoj2829】【信用卡凸包】【凸包】

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)

題解：

           把邊上的圓去掉然後求一遍凸包,最後再加上一個圓的周長即可.

           求頂點的時候注意角度問題.

代碼：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define N 100010
#define eps 1e-8
#define pie acos(-1)
using namespace std;
int n,cnt,top;
double ans,a,b,r;
struct use{double x,y;}p[N<<2],st[N<<2];
struct mat{double angle,x,y;}ma[N];
bool operator<(use a,use b){
  if (fabs(a.x-b.x)<eps) return a.y<b.y;
  else return a.x<b.x;
}
double operator*(use a,use b){
  return a.x*b.y-a.y*b.x;
}
use operator-(use a,use b){
  use c;
  c.x=a.x-b.x;
  c.y=a.y-b.y;
  return c;
}
double dis(use a){
  return sqrt(a.x*a.x+a.y*a.y);
}
use rotate(use a,double len,double angle){
  use t;
  t.x=a.x+len*cos(angle);
  t.y=a.y+len*sin(angle);
  return t; 
}
bool judge(use a,use b,use c){
  return (b-a)*(c-a)<-eps;
}
bool cmp(use a,use b){
  if (fabs((a-p[1])*(b-p[1]))<eps) return dis(a-p[1])<dis(b-p[1]);
  else return (a-p[1])*(b-p[1])>0; 
}
void graham(){
  top=0;
  for (int i=1;i<=cnt;i++)
     if (p[i]<p[1]) swap(p[1],p[i]);
  sort(p+2,p+cnt+1,cmp);    
  for (int i=1;i<=cnt;i++){
    while (top>1&&judge(st[top-1],st[top],p[i])) top--;  
    st[++top]=p[i];
  }
}
void getpoint(){
  for (int i=1;i<=n;i++)
    for (int k=0;k<4;k++){
       use t=rotate(use{ma[i].x,ma[i].y},b/2,k*pie/2+ma[i].angle);
       p[++cnt]=rotate(t,a/2,(k+1)*pie/2+ma[i].angle);
       swap(a,b);
    }
}
int main(){
  scanf("%d",&n);
  scanf("%lf%lf%lf",&a,&b,&r);
  a-=2*r;b-=2*r;ans=2*pie*r;
  for (int i=1;i<=n;i++)
    scanf("%lf%lf%lf",&ma[i].x,&ma[i].y,&ma[i].angle);
  getpoint();
  graham();
  st[++top]=st[1];
  for (int i=1;i<=top-1;i++)
    ans+=dis(st[i]-st[i+1]);
  printf("%.2lf\n",ans); 
}