关于样例2没过却AC这件事
查看原帖
关于样例2没过却AC这件事
410774
PuitungChan楼主2022/3/27 18:42

样例二要求输出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;
}

2022/3/27 18:42
加载中...