這道題BZOJ有權限,用學校的号A的,是以沒有傳送門,直接上題目描述~
(我才不會說在vijos上有也有這道題,因為我沒測試過,nanana)
題目描述
輸入樣例
2
6.0 2.0 0.0
0.0 0.0 0.0
2.0 -2.0 1.5707963268
輸出樣例
21.66
提示
本樣例中的2張信用卡的輪廓在上圖中用實線标出,如果視1.5707963268為Pi/2(pi為圓周率),則其凸包的周長為16+4*sqrt(2)
限制
時間:10s 空間 128MB
解題分析
這道題很裸的凸包,但是有不少細節需要處理:
1.信用卡的長和寬是個問題
因為題目說的圓滑處理就是把四角磨圓,而不是額外增一圈,是以給出的信用卡的長和寬其實是有多出來的,需要砍去兩個半徑的長度。
2.旋轉
還記得怎麼旋轉嗎,其實我也不知道,^_^
3.一個圓
同經典題Wall一樣,這道題也隻需在凸包周長上再加一個圓的周長就行了。
4.精度問題
由于旋轉涉及到三角函數,三角函數的大問題又是精度問題,是以建議用dcmp判斷,不然快排,可能會讓你開始懷疑 人生 C++
代碼
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,tot;
double a,b,R,ans,eps=;
int dcmp(double x)
{
if (fabs(x)<eps) return ;
return (x<)?-:;
}
struct data{
double x,y;
data (double x=,double y=):x(x),y(y){}
bool operator < (const data b) const{
return dcmp(x-b.x)<||(dcmp(x-b.x)==&&dcmp(y-b.y)<);
}
bool operator == (const data b) const{
return dcmp(x-b.x)==&&dcmp(y-b.y)==;
}
}p[],ch[],s[],c[];
data operator + (const data a,const data b) {return data(a.x+b.x,a.y+b.y);}
data operator - (const data a,const data b) {return data(a.x-b.x,a.y-b.y);}
double dot (const data a,const data b) {return a.x*b.x+a.y*b.y;}
double cross(const data a,const data b) {return a.x*b.y-a.y*b.x;}
double leng(const data a) {return sqrt(dot(a,a));}
data _Rotate(const data a,const double rad) {return data(a.x*cos(rad)-a.y*sin(rad),a.x*sin(rad)+a.y*cos(rad));}
//旋轉向量
inline void readd(double &x) //讀入優化
{
x=; int f=; double t=; char ch=getchar();
while ('0'>ch||ch>'9'){if (ch=='-') f=-f; ch=getchar();}
while ('0'<=ch&&ch<='9') {x=x*+ch-'0'; ch=getchar();}
if (ch=='.'){
ch=getchar();
while ('0'<=ch&&ch<='9') {t/=; x+=(ch-'0')*t; ch=getchar();}
}
x*=f;
}
void _init()
{
scanf("%d",&n); m=;
readd(b); readd(a); readd(R);
a-=*R; b-=*R;
s[]=data(a/,b/); s[]=data(a/,-b/); s[]=data(-a/,b/); s[]=data(-a/,-b/); //友善編寫
for (int i=;i<=n;i++)
{
double x,y,z; readd(x); readd(y); readd(z);
for (int j=;j<;j++) c[++m]=data(x,y)+_Rotate(s[j],z);
}
}
void _work() //排序,由于本人強迫症,還去了個重。
{
sort(c+,c+m+);
int i=,j; n=;
while (i<=m)
{
j=i+; ch[++n]=c[i];
while (j<=m&&c[i]==c[j]) j++;
i=j;
}
}
void _solve()
{
_work(); tot=;
for (int i=;i<=n;i++)
{
while (tot>&&dcmp(cross(p[tot]-p[tot-],ch[i]-p[tot-]))<=) tot--;
p[++tot]=ch[i];
}
int k=tot;
for (int i=n-;i>;i--)
{
while (tot>k&&dcmp(cross(p[tot]-p[tot-],ch[i]-p[tot-]))<=) tot--;
p[++tot]=ch[i];
}
ans=R**;
for (int i=;i<tot;i++) ans+=leng(p[i+]-p[i]);
printf("%0.2lf",ans);
}
int main()
{
_init();
_solve();
return ;
}
PS:本部落格過于簡陋,再加上作者fhj水準過菜,如果各位神犇有建議,請多多指出,謝謝!