想法是将每个信用卡的四个边界点求出来,求凸包之后再加上一个圆的周长
#include <bits/stdc++.h>
#define maxn 100010
#define double long double
#define eps 1e-7
using namespace std;
int n;
double a,b,rr;
const double pi = acos(-1);
struct node { //表示坐标点
double x, y;
node () {}
node(double a, double b) : x(a), y(b) {}
bool operator < (const node &a) const {
if (fabs(x - a.x) > eps){
if(x - a.x < 0) return true;
else return false;
} //先按照横坐标排序
if(y < a.y) return true;
else return false;
}
node operator - (const node &a) const {
return node(x - a.x, y - a.y); //这里是返回向量
}
} p[maxn], ps[maxn];
int cmp(double x) {
if (fabs(x) < eps) return 0;
return x > 0 ? 1 : -1;
}
double rtoa(double rad){
// cout << rad << ' ' << rad / pi * 180.0 << endl;
return rad * 180.0 / pi;
}
double ator(double angle){
return angle * pi / 180.0;
}
node change(double r,double alpha, double beta, double tx,double ty){ //某个点旋转
return (node){r * cos(ator(alpha + beta)) + tx, r * sin(ator(alpha + beta)) + ty};
}
double dis(node a, node b) {
return sqrt(abs(a.x - b.x) * abs(a.x - b.x) + abs(a.y - b.y) * abs(a.y - b.y));
}
double cp(node a, node b) { //叉积操作
return a.x * b.y - a.y * b.x;
}
int andrew() {
sort(p + 1, p + 1 + n);
// puts("");
// swap(p[1],p[3]);
// swap(p[1],p[4]);
// for(int i = 1; i <= n; i++){
// printf("%Lf %Lf\n", p[i].x , p[i].y);
// }
// cout << n << endl;
int len = 0;
for (int i = 1; i <= n; i++) {
while (len > 1 && cmp(cp(ps[len] - ps[len - 1], p[i] - ps[len - 1])) < 0)
len--; //将向量进行比对
ps[++len] = p[i];
}
// cout << len << endl;
//因为比较的是要插的点和没插的点的向量
int k = len;
for (int i = n - 1; i >= 1; i--) { //再扫一遍
while (len > k && cmp(cp(ps[len] - ps[len - 1], p[i] - ps[len - 1])) < 0)
len--;
ps[++len] = p[i];
}
return len;
}
double tx,ty,rad;
double angle[5];
int cnt = 0;
double c;
int main() {
ios::sync_with_stdio(false);
cin >> n;
cin >> a >> b >> rr;
a /= 2,b /= 2;
angle[1] = rtoa(atan2(a , b));
angle[2] = rtoa(atan2(a , -b));
// cout << rtoa(atan(a -b)) << endl;
angle[3] = rtoa(atan2(-a , -b));
angle[4] = rtoa(atan2(-a , b));
c = sqrt(a * a + b * b) / 1.0; //倍数
for(int i = 1; i <= n; i++){
cin >> tx >> ty >> rad;
for(int j = 1; j <= 4; j++){
// cout << angle[j] << endl;
p[++cnt] = change(c, angle[j], rtoa(rad), tx, ty);
// cout << p[cnt].x << ' ' << p[cnt].y << endl;
}
}
n = cnt;
// for(int i = 1; i <= n; i++){
// cout << p[i].x << ' ' << p[i].y << endl;
// }
int tmp = andrew();
double ans = 0;
// cout << tmp - 1 << endl;
for(int i = 1; i < tmp - 1; i++){
ans += dis(ps[i], ps[i + 1]);
}
ans += dis(ps[tmp - 1], ps[1]);
ans += 2.0 * rr * pi;
printf("%.2Lf", ans);
return 0;
}