QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#324878 | #6763. Triangle Pendant | mshcherba | WA | 3ms | 3880kb | C++20 | 5.6kb | 2024-02-11 01:04:21 | 2024-02-11 01:04:22 |
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};
}
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};
}
};
// Returns the squared absolute value
db sq(const Pt& p)
{
return p.x * p.x + p.y * p.y;
}
// Returns the absolute value
db abs(const Pt& p)
{
return sqrt(sq(p));
}
// Returns -1 for negative numbers, 0 for zero,
// and 1 for positive numbers
int sgn(db x)
{
return (EPS < x) - (x < -EPS);
}
// Returns `p` rotated counter-clockwise by `a`
Pt rot(const Pt& p, db a)
{
db co = cos(a), si = sin(a);
return {p.x * co - p.y * si,
p.x * si + p.y * co};
}
// Returns `p` rotated counter-clockwise by 90
Pt perp(const Pt& p)
{
return {-p.y, p.x};
}
// Returns the dot product of `p` and `q`
db dot(const Pt& p, const Pt& q)
{
return p.x * q.x + p.y * q.y;
}
// Returns the angle between `p` and `q` in [0, pi]
db angle(const Pt& p, const Pt& q)
{
return acos(clamp(dot(p, q) / abs(p) /
abs(q), (db)-1.0, (db)1.0));
}
// Returns the cross product of `p` and `q`
db cross(const Pt& p, const Pt& q)
{
return p.x * q.y - p.y * q.x;
}
// Positive if R is on the left side of PQ,
// negative on the right side,
// and zero if R is on the line containing PQ
db orient(const Pt& p, const Pt& q, const Pt& r)
{
return cross(q - p, r - p) / abs(q - p);
}
// Checks if argument of `p` is in [-pi, 0)
bool half(const Pt& p)
{
assert(sgn(p.x) != 0 || sgn(p.y) != 0);
return sgn(p.y) == -1 ||
(sgn(p.y) == 0 && sgn(p.x) == -1);
}
// Polar sort of vectors in `v` around `o`
void polarSortAround(const Pt& o, vector<Pt>& v)
{
sort(ALL(v), [o](Pt p, Pt q)
{
p = p - o;
q = q - o;
bool hp = half(p), hq = half(q);
if (hp != hq)
return hp < hq;
int s = sgn(cross(p, q));
if (s != 0)
return s == 1;
return sq(p) < sq(q);
});
}
// Example:
// cout << a + b << " " << a - b << "\n";
ostream& operator<<(ostream& os, const Pt& p)
{
return os << "(" << p.x << "," << p.y << ")";
}
// Returns circle-circle intersection points
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)
{
// assuming the circles don't coincide
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};
}
void print(db a, db b, db c, int i)
{
if (i == 0)
cout << a << " " << b << " " << c << "\n";
else if (i == 1)
cout << b << " " << c << " " << a << "\n";
else
cout << c << " " << a << " " << b << "\n";
}
db getMedian(db a, db b, db c)
{
return sqrt(2 * (b * b + c * c) - a * a) / 2;
}
db getCos(db a, db b, db c)
{
db res = (b * b + c * c - a * a) / (2 * b * c);
assert(-1 - EPS < res && res < 1 + EPS);
return res;
}
db getThirdSide(db b, db c, db co)
{
return sqrt(b * b + c * c - 2 * b * c * co);
}
bool solve1(db x, db y, db z, db a, db b, db c, int i)
{
Pt A = {0, 0}, B = {c, 0}, C = circleCircle(A, b, B, a)[0];
Pt M = (A + B + C) / 3;
Pt D = A + (A - M) * (x / abs(A - M));
if (abs(B - D) > y + EPS || abs(C - D) > z + EPS)
return false;
print(-x, dot(B - D, M - D) / (-abs(M - D)), dot(C - D, M - D) / (-abs(M - D)), i);
return true;
}
bool solve2(db x, db y, db z, db a, db b, db c, int i)
{
if (2 * max({x, y, c}) > x + y + c + EPS)
return false;
Pt A = {0, 0}, B = {c, 0}, C = circleCircle(A, b, B, a)[0];
Pt M = (A + B + C) / 3;
auto Ds = circleCircle(A, x, B, y);
Pt D = SZ(Ds) == 2 && abs(Ds[1] - C) > abs(Ds[0] - C) ? Ds[1] : Ds[0];
if (sgn(orient(D, M, A)) * sgn(orient(D, M, B)) >= 0)
return false;
if (abs(D - C) > z + EPS)
return false;
print(dot(A - D, M - D) / (-abs(M - D)), dot(B - D, M - D) / (-abs(M - D)), dot(C - D, M - D) / (-abs(M - D)), i);
return true;
}
pair<db, db> getH(db x, db y, db z, db a, db b, db c)
{
db ma = getMedian(a, y, z), mA = getMedian(a, b, c);
db cosA = getCos(ma, x, mA);
db l = getThirdSide(2 * mA / 3, x, cosA);
cosA = getCos(2 * mA / 3, x, l);
return {-x * cosA, l};
}
void solve()
{
db x, y, z, a, b, c;
cin >> x >> y >> z >> a >> b >> c;
int ok1 = 0;
if (solve1(x, y, z, a, b, c, 0))
ok1++;
if (solve1(y, z, x, b, c, a, 1))
ok1++;
if (solve1(z, x, y, c, a, b, 2))
ok1++;
assert(ok1 <= 1);
if (ok1)
return;
int ok2 = 0;
if (solve2(x, y, z, a, b, c, 0))
ok2++;
if (solve2(y, z, x, b, c, a, 1))
ok2++;
if (solve2(z, x, y, c, a, b, 2))
ok2++;
assert(ok2 <= 1);
if (ok2)
return;
auto [ans1, l1] = getH(x, y, z, a, b, c);
auto [ans2, l2] = getH(y, z, x, b, c, a);
auto [ans3, l3] = getH(z, x, y, c, a, b);
assert(abs(l2 - l1) < EPS && abs(l3 - l1) < EPS);
cout << ans1 << " " << ans2 << " " << ans3 << "\n";
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout << fixed << setprecision(15);
int t;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3872kb
input:
2 1 1 1 1 1 1 2 3 3 1 1 1
output:
-0.816496580927726 -0.816496580927726 -0.816496580927726 -2.000000000000000 -2.866025403784439 -2.866025403784439
result:
ok 6 numbers
Test #2:
score: -100
Wrong Answer
time: 3ms
memory: 3880kb
input:
1000 21 2 14 12 13 4 29 19 13 15 10 17 29 24 15 29 24 23 29 17 30 18 9 25 27 24 30 16 4 15 28 13 17 12 21 16 16 22 10 22 15 8 15 23 24 23 27 13 26 3 27 15 16 17 5 8 20 17 6 12 24 14 13 15 19 13 27 22 18 18 23 30 22 18 14 11 29 28 7 13 22 22 17 11 19 9 16 22 20 17 21 14 20 6 29 25 20 10 19 9 27 27 17...
output:
-13.352348999857671 -2.935856727586833 -2.000000000000000 -12.241826659011300 -22.146476218003027 -16.076204705476879 -28.027431433359670 -18.318582636182796 -8.243362186282258 -27.266119651334353 -13.159319584325646 -26.882525397692707 -26.534933366925674 -22.066632132649339 -29.616079568529663 -26...
result:
wrong answer 1st numbers differ - expected: '-2.93586', found: '-13.35235', error = '3.54802'