当我尝试输出每次将要加入点集的四个点时,发现在样例二的第一张卡时,左上角的顶点为0.894427 2.68328 。
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<vector>
using namespace std;
struct node{
double x;
double y;
};
int n;
vector<node> point;
vector<node> work;
double a,b,r;
double check(node a1,node a2,node b1,node b2){
return (a2.x-a1.x)*(b2.y-b1.y)-(b2.x-b1.x)*(a2.y-a1.y);
}
double dist(node a,node b){
return sqrt((a.y-b.y)*(a.y-b.y)+(a.x-b.x)*(a.x-b.x));
}
bool cmp(node a,node b){
double tmp=check(point[1],a,point[1],b);
if(tmp>0)
return 1;
if(tmp==0&&dist(point[1],a)<dist(point[1],b)){
return 1;
}
return 0;
}
void input(){
node k;
k.x=k.y=0;
point.push_back(k);
int _n;
cin>>_n;
double a,b,r;
cin>>a>>b>>r;
for(int i=1;i<=_n;i++){
double x,y,sita;
cin>>x>>y>>sita;
node base[5];
base[1].x=x-b/2+r;base[1].y=y+a/2-r;
base[2].x=x-b/2+r;base[2].y=y-a/2+r;
base[3].x=x+b/2-r;base[3].y=y+a/2-r;
base[4].x=x+b/2-r;base[4].y=y-a/2+r;
//for(int j=1;j<=4;j++){
// cout<<base[j].x<<" "<<base[j].y<<"\n";
//}
node newadd[5];
for(int j=1;j<=4;j++){
double sit=atan2(base[j].y,base[j].x);
// cout<<"sit:"<<sit<<"\n";
double R=sqrt(pow(b-2*r,2)/4+pow(a-2*r,2)/4);
sit+=sita;
// cout<<"sit after sita:"<<sit<<"\n";
newadd[j].x=R*cos(sit);
newadd[j].y=R*sin(sit);
// cout<<newadd[j].x<<" "<<newadd[j].y<<"\n";
point.push_back(newadd[j]);
}
}
n=4*_n;
}
double Do(){
for(int i=1;i<=n;i++){
if(i!=1){
if(point[i].y<point[1].y){
swap(point[1],point[i]);
}
else if(point[i].y==point[1].y){
if(point[i].x<point[1].x){
swap(point[1],point[i]);
}
}
}
}
sort(point.begin()+2,point.end(),cmp);
//for(int i=1;i<=n;i++){
// cout<<point[i].x<<" "<<point[i].y<<"\n";
//}
work.push_back(point[1]);
for(int i=2;i<=n;i++){
while(work.size()>=2&&check(work[work.size()-2],work[work.size()-1],work[work.size()-1],point[i])<=0)
work.pop_back();
work.push_back(point[i]);
/*for(int j=0;j<work.size();j++){
cout<<work[j].x<<" "<<work[j].y<<"\n";
}
cout<<"\n";
*/
}
work.push_back(point[1]);
/*for(int j=0;j<work.size();j++){
cout<<work[j].x<<" "<<work[j].y<<"\n";
}*/
double ans=0;
for(int i=0;i<work.size()-1;i++){
ans+=dist(work[i],work[i+1]);
}
return ans;
}
int main(){
input();
printf("%.2lf",Do()+2*acos(-1)*r);
}