题目链接:https://www.luogu.org/problemnew/show/P3829
题目大意:中文题,易理解。
思路:Fuck!!精度卡了我一页的WA...(还是太菜了)经过简单的草图,如下图所示:随便举一个例子,然后发现,周长就是里面的小的多边形的周长+圆的周长。至于具体的证明,这不是显而易见的么??然后就是求出每个矩形的四个点,然后求出凸包,就行了,简单的板子题,半个小时搞定!
好了好了!!板子确实好写,主要是精度!!四个点的坐标。。一开始我用的:
Ang1=atan2(b,a);Dots[++Ecnt]=Point(x+C*cos(Ang+Ang1),y+C*sin(Ang+Ang1));
Ang1=atan2(b,-a);Dots[++Ecnt]=Point(x+C*cos(Ang+Ang1),y+C*sin(Ang+Ang1));
Ang1=atan2(-b,a);Dots[++Ecnt]=Point(x+C*cos(Ang+Ang1),y+C*sin(Ang+Ang1));
Ang1=atan2(-b,-a);Dots[++Ecnt]=Point(x+C*cos(Ang+Ang1),y+C*sin(Ang+Ang1));
结果WA了5,6,10三个测试点。我还以为是我板子的问题,调了一节课(毛概一整节课都没调出来啊)。回寝室之后继续调,结果还是没有跳出来,我又写了一个Jaris法,还是5,6,10测试点。。这时我还以为是板子的问题(呜呜呜。。。
结果早上试着用其他方法得到四个点,发现就过了。。。万恶的精度啊!!不过也是,三角函数用了个遍,精度肯定损失到爆炸...
ACCode:
// luogu-judger-enable-o2
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<map>
#include<set>
#include<deque>
#include<queue>
#include<stack>
#include<bitset>
#include<string>
#include<fstream>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
#define Pair pair<int,int>
//#define max(a,b) (a)>(b)?(a):(b)
//#define min(a,b) (a)<(b)?(a):(b)
#define clean(a,b) memset(a,b,sizeof(a))// 水印
//std::ios::sync_with_stdio(false);
// register
const int MAXN=1e4+10;
const int INF32=0x3f3f3f3f;
const ll INF64=0x3f3f3f3f3f3f3f3f;
const int MOD=1e9+7;
const double EPS=1.0e-8;
const double PI=acos(-1.0);
struct Point{
double x,y;
Point(double _x=0,double _y=0){
x=_x;y=_y;
}
friend Point operator + (const Point &a,const Point &b){
return Point(a.x+b.x,a.y+b.y);
}
friend Point operator - (const Point &a,const Point &b){
return Point (a.x-b.x,a.y-b.y);
}
friend double operator ^ (const Point &a,const Point &b){
return a.x*b.y-a.y*b.x;
}
friend bool operator == (const Point &a,const Point &b){
return fabs(a.x-b.x)<EPS&&fabs(a.y-b.y)<EPS;
}
};
struct V{
Point start,end;
V(Point _start=Point(0,0),Point _end=Point(0,0)){
start=_start;end=_end;
}
};
Point Dots[MAXN<<2];
Point Stk[MAXN<<2];int Top;
double A,B,R;
int N,Ecnt;
double Distance(Point a,Point b){
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
double Prellel(double key){
return fabs(key)<EPS?0:key;
}
int Cmp(Point a,Point b){
double res=Prellel((a-Dots[1])^(b-Dots[1]));
if(res>0) return 1;
if(res==0&&Distance(a,Dots[1])<Distance(b,Dots[1])) return 1;
return 0;
}
int Cmp2(Point a,Point b){
return (a.y<b.y||(a.y==b.y&&a.x<b.x));
}
int Judge(int k,int i){
if(Dots[i].y<Dots[k].y||(Dots[i].y==Dots[k].y&&Dots[i].x<Dots[k].x)) return 1;
return 0;
}
void Graham(){
int k=1;
for(int i=2;i<=Ecnt;++i){
// cout<<"DOts: "<<Dots[i].x<<" "<<Dots[i].y<<endl;
if(Judge(k,i)) k=i;
}swap(Dots[1],Dots[k]);
sort(Dots+2,Dots+1+Ecnt,Cmp);
Top=0;Stk[++Top]=Dots[1];
for(int i=2;i<=Ecnt;++i){
while(Top>=3&&((Dots[i]-Stk[Top-1])^(Stk[Top]-Stk[Top-1]))>=0) --Top;
// while(Top>=3&&((Stk[Top]-Stk[Top-1])^(Dots[i]-Stk[Top-1]))<EPS) --Top;
Stk[++Top]=Dots[i];
}//Stk[Top+1]=Stk[1];
}
void Jarvis(){
int len;Top=0;
sort(Dots+1,Dots+1+N,Cmp2);
Stk[++Top]=Dots[1];Stk[++Top]=Dots[2];
for(int i=3;i<=N;++i){
while(Top>=2&&((Dots[i]-Stk[Top-1])^(Stk[Top-1]-Stk[Top]))>=0) --Top;
Stk[++Top]=Dots[i];
}int Bot=Top;
for(int i=N-1;i>0;--i){
while(Top>Bot&&((Dots[i]-Stk[Top-1])^(Stk[Top-1]-Stk[Top]))>=0) --Top;
Stk[++Top]=Dots[i];
}Stk[Top+1]=Stk[1];
}
Point rotate(Point a,double Ang){
double c=cos(Ang),s=sin(Ang);
return Point(a.x*c-a.y*s,a.x*s+a.y*c);
}
int main(){
while(~scanf("%d",&N)){
scanf("%lf%lf%lf",&A,&B,&R);
// double a=A/2.0,b=B/2.0,r=R;
// double a=A/2.0-R,b=B/2.0-R;
double a=A-R*2.0,b=B-R*2.0;
// cout<<a<<" "<<b<<endl;
double C=sqrt(a*a+b*b);
double x,y,Ang;Ecnt=0;
double Ang1;
// cout<<"C is : "<<C<<endl;
for(int i=1;i<=N;++i){
scanf("%lf%lf%lf",&x,&y,&Ang);
Point k(x,y),d,v;double rad=Ang;
d=Point(x+b/2,y-a/2),v=rotate(k-d,rad),Dots[++Ecnt]=k+v;
d=Point(x-b/2,y-a/2),v=rotate(k-d,rad),Dots[++Ecnt]=k+v;
d=Point(x+b/2,y+a/2),v=rotate(k-d,rad),Dots[++Ecnt]=k+v;
d=Point(x-b/2,y+a/2),v=rotate(k-d,rad),Dots[++Ecnt]=k+v;
// Dots[++Ecnt]=rotate(Point(a-r,b-r),Ang)+Point(x,y);
// Dots[++Ecnt]=rotate(Point(r-a,b-r),Ang)+Point(x,y);
// Dots[++Ecnt]=rotate(Point(r-a,r-b),Ang)+Point(x,y);
// Dots[++Ecnt]=rotate(Point(a-r,r-b),Ang)+Point(x,y);
// Ang1=atan2(b,a);Dots[++Ecnt]=Point(x+C*cos(Ang+Ang1),y+C*sin(Ang+Ang1));
// Ang1=atan2(b,-a);Dots[++Ecnt]=Point(x+C*cos(Ang+Ang1),y+C*sin(Ang+Ang1));
// Ang1=atan2(-b,a);Dots[++Ecnt]=Point(x+C*cos(Ang+Ang1),y+C*sin(Ang+Ang1));
// Ang1=atan2(-b,-a);Dots[++Ecnt]=Point(x+C*cos(Ang+Ang1),y+C*sin(Ang+Ang1));
}Graham();//Jarvis();
double ans=2.0*R*PI;
for(int i=2;i<=Top;++i){
ans+=Distance(Stk[i],Stk[i-1]);
// cout<<"the Stk is : "<<ans<<" "<<Stk[i].x<<" "<<Stk[i].y<<endl;
}ans+=Distance(Stk[1],Stk[Top]);
printf("%.2lf\n",ans);
}
}
/*
*/