[SHOI2012] 信用卡凸包
一道将做法写在题目里的题.
由题目可知, 本题是一道凸包, 然后我们将图画出来之后, 可以发现每一段直线都是相邻两段圆弧的切线, 所以我们就只需要去掉圆弧, 求个凸包, 最后再加上一个圆的周长就行了.
这个插入矩形巨神笔, 而且注意不要读错题, 是 逆时针 转.
卡我半天的水题, 日!
\(code:\)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int read() {
int x = 0, f = 1;
char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
return x * f;
}
const int N = 1e5 + 5;
const double Pi = 3.141592653589793, eps = 1e-8;
struct Vec {
double x, y;
Vec(double a = 0, double b = 0) {
x = a, y = b;
}
bool operator < (const Vec &a) const {
if (x == a.x) return y < a.y;
return x < a.x;
}
Vec operator - (const Vec &a) const {
return Vec(x - a.x, y - a.y);
}
double operator * (const Vec &a) const {
return x * a.y - a.x * y;
}
double d(Vec a) {
return sqrt((x - a.x) * (x - a.x) + (y - a.y) * (y - a.y));
}
} p[N], h[N];
bool Check(Vec a, Vec b, Vec c) {
return (a - b) * (c - a) <= 0;
}
Vec stk[N];
int top;
void Andrew(int n) {
sort(p + 1, p + n + 1);
stk[++top] = p[1];
for (int i = 2; i <= n; i++) {
while (top > 1&& Check(stk[top], stk[top - 1], p[i])) top--;
stk[++top] = p[i];
}
int tmp = top;
for (int i = n - 1; i > 0; i--) {
while (top > tmp && Check(stk[top], stk[top - 1], p[i])) top--;
stk[++top] = p[i];
}
for (int i = 1; i <= top; i++) h[i] = stk[i];
}
int n, tot;
double a, b, r, l, t, ans;
void Add(double x, double y, double s) {
p[++tot] = Vec(x + l * cos(s), y + l * sin(s));
p[++tot] = Vec(x - l * cos(s), y - l * sin(s));
}
int main() {
n = read();
scanf("%lf%lf%lf", &a, &b, &r);
a -= 2 * r, b -= 2 * r;
l = sqrt(a * a + b * b) / 2, t = atan(a / b);
double x, y, z;
for (int i = 1; i <= n; i++) {
scanf("%lf%lf%lf", &x, &y, &z);
Add(x, y, z + t);
Add(x, y, z - t);
}
Andrew(tot);
for (int i = 1; i < top; i++) ans += h[i].d(h[i + 1]);
printf("%.2lf", ans + 2 * Pi * r);
return 0;
}