样例二要求输出41.6,我代码输出49.6,然后调不出bug了,抱着试试能过几个点的心态交了上去,结果全a了 ???这是为什么
(请忽略我那一堆头文件)
//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <stack>
#include <vector>
#include <queue>
#include <list>
#include <map>
#include <cmath>
#include <utility>
#include <algorithm>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
typedef unsigned long long ull;
typedef long long ll;
using namespace std;
const int N = 10010;
const double pi = acos(-1), eps = 1e-11;
int n, cnt = 0;
double a, b, r, x, y, rad;
typedef pair<double, double> PDD;
PDD p[N * 4];
double dx[] = { 1,1,-1,-1 }, dy[] = { 1,-1,-1,1 };
double len(PDD a, PDD b)
{
double x = a.first - b.first, y = a.second - b.second;
return sqrt(x * x + y * y);
}
void add(double x, double y, double rad)
{
for (int i = 0; i < 4; ++i)
{
double tx, ty, s = sin(rad) ,c = cos(rad);
tx = x + (dx[i] * b * c - dy[i] * a * s);
ty = y + (dy[i] * a * c + dx[i] * b * s);
p[cnt++] = { tx,ty };
}
}
bool use[N * 4]{};
int tb[N * 4];
PDD operator - (PDD a, PDD b)
{
return { a.first - b.first,a.second - b.second };
}
double cross(PDD v, PDD u)
{
return v.first * u.second - u.first * v.second;
}
double area(int aa, int bb, PDD c)
{
PDD a = p[aa], b = p[bb];
PDD v = a - b, u = c - b;
return cross(v, u);
}
bool cmp(PDD a, PDD b)
{
if (a.first - b.first < -eps) return true;
if (fabs(a.first - b.first) < eps)
if (a.second - b.second > eps) return true;
return false;
}
double andrew()
{
sort(p, p + cnt,cmp);
int c = 0;
for (int i = 0; i < cnt; ++i)
{
while (c > 1 && area(tb[c - 1], tb[c - 2], p[i]) >= eps) use[tb[--c]] = false;
tb[c++] = i;
use[i] = true;
}
use[0] = false;
for (int i = cnt - 1; i >= 0; --i)
{
if (use[i]) continue;
while (c > 1 && area(tb[c - 1], tb[c - 2], p[i]) >= eps) c--;
tb[c++] = i;
}
double res = 0;
for (int i = 1; i < c; ++i)
{
res += len(p[tb[i]], p[tb[i - 1]]);
}
return res;
}
int main()
{
cin >> n >> a >> b >> r;
a = a / 2 - r;
b = b / 2 - r;
for (int i = 0; i < n; ++i)
{
cin >> x >> y >> rad;
add(x, y, rad);
}
printf("%.2lf",pi * 2 * r + andrew());
return 0;
}