QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#358122#3173. Cakey McCakeFacePetroTarnavskyi#WA 0ms3740kbC++202.3kb2024-03-19 17:24:592024-03-19 17:24:59

Judging History

This is the latest submission verdict.

  • [2024-03-19 17:24:59]
  • Judged
  • Verdict: WA
  • Time: 0ms
  • Memory: 3740kb
  • [2024-03-19 17:24:59]
  • Submitted

answer

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;

const db EPS = 1e-9;

struct Pt
{
	db x, y;
	Pt operator-(const Pt& p) const
	{
		return {x - p.x, y - p.y};
	}
};

db sq(const Pt& p)
{
	return p.x * p.x + p.y * p.y;
}

db abs(const Pt& p)
{
	return sqrt(sq(p));
}

int sgn(db x)
{
	return (EPS < x) - (x < -EPS);
}

Pt perp(const Pt& p)
{
	return {-p.y, p.x};
}

db dot(const Pt& p, const Pt& q)
{
	return p.x * q.x + p.y * q.y;
}

db cross(const Pt& p, const Pt& q)
{
	return p.x * q.y - p.y * q.x;
}

db orient(const Pt& p, const Pt& q, const Pt& r)
{
	return cross(q - p, r - p) / abs(q - p);
}

struct Line
{
	Pt n;
	db c;
	Line(const Pt& p, const Pt& q):
		n(perp(q - p)), c(-dot(n, p)) {}
	db side(const Pt& p) const
	{
		return dot(n, p) + c;
	}
	db dist(const Pt& p) const
	{
		return abs(side(p)) / abs(n);
	}
};

vector<Pt> convexHull(vector<Pt> v)
{
	if (SZ(v) <= 1)
		return v;
	sort(ALL(v), [](const Pt& p, const Pt& q)
	{
		int dx = sgn(p.x - q.x);
		if (dx != 0)
			return dx < 0;
		return sgn(p.y - q.y) < 0;
	});
	vector<Pt> lower, upper;
	for (const Pt& p : v)
	{
		while (SZ(lower) > 1
			&& sgn(orient(lower[SZ(lower) - 2],
			lower.back(), p)) <= 0)
			lower.pop_back();
		while (SZ(upper) > 1
			&& sgn(orient(upper[SZ(upper) - 2],
			upper.back(), p)) >= 0)
			upper.pop_back();
		lower.PB(p);
		upper.PB(p);
	}
	reverse(ALL(upper));
	lower.insert(lower.end(), next(upper.begin()),
		prev(upper.end()));
	return lower;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout << fixed << setprecision(15);
	int n, r;
	cin >> n >> r;
	vector<Pt> v(n);
	for (Pt& p : v)
		cin >> p.x >> p.y;
	v = convexHull(v);
	n = SZ(v);
	int ptr = 0;
	db ans = 47.0 * r;
	FOR(i, 0, n)
	{
		ptr = max(ptr, i + 1);
		Line l(v[i], v[(i + 1) % n]);
		while (sgn(l.dist(v[(ptr + 1) % n]) - l.dist(v[ptr % n])) > 0)
		{
			ptr++;
		}
		ans = min(ans, l.dist(v[ptr % n]));
	}
	cout << ans << "\n";
	return 0;
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3740kb

input:

5
5
0 10 12 20 30
1 5 17 27 50

output:

29.393940437441081

result:

wrong answer 1st lines differ - expected: '5', found: '29.393940437441081'