QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#346004 | #3196. Bribing Eve | PetroTarnavskyi# | WA | 0ms | 3852kb | C++20 | 2.7kb | 2024-03-07 19:23:12 | 2024-03-07 19:23:12 |
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 long 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};
}
Pt operator-(const Pt& p) const
{
return {x - p.x, y - p.y};
}
Pt operator*(db d) const
{
return {x * d, y * d};
}
Pt operator/(db d) const
{
return {x / d, y / d};
}
};
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};
}
vector<Pt> circleCircle(const Pt& o1, db r1,
const Pt& o2, db r2)
{
Pt d = o2 - o1;
db d2 = sq(d);
if (sgn(d2) == 0)
{
assert(sgn(r2 - r1) != 0);
return {};
}
db pd = (d2 + r1 * r1 - r2 * r2) / 2;
db h2 = r1 * r1 - pd * pd / d2;
if (sgn(h2) == -1)
return {};
Pt p = o1 + d * pd / d2;
if (sgn(h2) == 0)
return {p};
Pt h = perp(d) * sqrt(h2 / d2);
return {p - h, p + h};
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
VI l(n), sufSum(n), sufMx(n), rMin(n);
for (int& li : l)
cin >> li;
Pt target;
cin >> target.x >> target.y;
sufSum[n - 1] = l[n - 1];
sufMx[n - 1] = l[n - 1];
RFOR(i, n - 1, 0)
{
sufSum[i] = sufSum[i + 1] + l[i];
sufMx[i] = max(sufMx[i + 1], l[i]);
}
FOR(i, 0, n)
{
rMin[i] = max(0, 2 * sufMx[i] - sufSum[i]);
}
db absTarget = abs(target);
if (sgn(absTarget - rMin[0]) < 0)
target = target * (rMin[0] / absTarget);
else if (sgn(absTarget - sufSum[0]) > 0)
target = target * (sufSum[0] / absTarget);
Pt p = {0, 0};
vector<Pt> ans;
FOR(i, 0, n - 1)
{
Pt q = {p.x + l[i], p.y};
db dist = abs(target - q);
// rMin[i + 1] <= dist && dist <= sufSum[i + 1]
if (sgn(rMin[i + 1] - dist) <= 0 && sgn(dist - sufSum[i + 1]) <= 0)
{
p = q;
}
else
{
vector<Pt> vec;
vec = circleCircle(p, l[i], target, sufSum[i + 1]);
if (!vec.empty())
p = vec[0];
else
{
assert(rMin[i + 1] != 0);
vec = circleCircle(p, l[i], target, rMin[i + 1]);
assert(!vec.empty());
p = vec[0];
}
}
ans.PB(p);
}
ans.PB(target);
for (const Pt& q : ans)
cout << q.x << " " << q.y << "\n";
assert(sgn(abs(ans[0]) - l[0]) == 0);
FOR(i, 0, n - 1)
assert(sgn(abs(ans[i + 1] - ans[i]) - l[i + 1]) == 0);
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3852kb
input:
5 7 7 11 10 8 5 1 1 12 12
output:
7 0 14 0 21.6053 7.94733 12.3801 4.0877 5 1
result:
wrong answer 1st lines differ - expected: '3 4', found: '7 0'