QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#358122 | #3173. Cakey McCakeFace | PetroTarnavskyi# | WA | 0ms | 3740kb | C++20 | 2.3kb | 2024-03-19 17:24:59 | 2024-03-19 17:24:59 |
Judging History
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'