QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#513018 | #9168. Square Locator | ucup-team4361# | WA | 1ms | 3672kb | C++14 | 3.3kb | 2024-08-10 16:37:48 | 2024-08-10 16:37:49 |
Judging History
answer
#include <bits/stdc++.h>
#define LL long long
#define ull unsigned long long
#define F(i, j, k) for (int i = j; i <= k; ++i)
#define DF(i, j, k) for (int i = j; i >= k; --i)
using namespace std;
template <typename T> inline void read(T &n) {
T w = 1;
n = 0;
char ch = getchar();
while (!isdigit(ch) && ch != EOF) {
if (ch == '-') w = -1;
ch = getchar();
}
while (isdigit(ch) && ch != EOF) {
n = (n << 3) + (n << 1) + (ch & 15);
ch = getchar();
}
n *= w;
}
template <typename T> inline void write(T x) {
T l = 0;
ull y = 0;
if (!x) { putchar(48); return; }
if (x < 0) { x = -x; putchar('-'); }
while (x) { y = y * 10 + x % 10; x /= 10; ++l; }
while (l) { putchar(y % 10 + 48); y /= 10; --l; }
}
template <typename T> inline void writes(T x) {
write(x);
putchar(' ');
}
template <typename T> inline void writeln(T x) {
write(x);
puts("");
}
template <typename T> inline void checkmax(T &a, T b) { a = a > b ? a : b; }
template <typename T> inline void checkmin(T &a, T b) { a = a < b ? a : b; }
const double Eps = 1e-8;
bool f = 0;
LL A, B, C, D;
inline double check(double now) {
double xa = 0, ya = sqrt(A);
double csita = (D - A - now * now) / (2.0 * sqrt(A) * now);
double yd = ya + csita * now;
double xd = sqrt(now * now - csita * now * csita * now);
double xb1 = yd - ya, yb1 = ya - xd;
double xb2 = ya - yd, yb2 = ya + xd;
return min(xb1 * xb1 + yb1 * yb1, xb2 * xb2 + yb2 * yb2);
}
inline void work(double now) {
double xa = 0, ya = sqrt(A);
double csita = (D - A - now * now) / (2.0 * sqrt(A) * now);
double yd = ya + csita * now;
double xd = sqrt(now * now - csita * now * csita * now);
double xb1 = yd - ya, yb1 = ya - xd;
double xb2 = ya - yd, yb2 = ya + xd;
double xb, yb;
if (xb1 * xb1 + yb1 * yb1 < xb2 * xb2 + yb2 * yb2) {
xb = xb1;
yb = yb1;
}
else {
xb = xb2;
yb = yb2;
}
double xc = xb + xd - xa, yc = yb + yd - ya;
if ((LL)round(xc) * (LL)round(xc) + (LL)round(yc) * (LL)round(yc) == C
&& (round(xa) != round(xb) || round(ya) != round(yb)))
{
f = 1;
cout << (LL)round(ya) << ' ';
cout << (LL)round(xb) << ' ' << (LL)round(yb) << ' ';
cout << (LL)round(xc) << ' ' << (LL)round(yc) << ' ';
cout << (LL)round(xd) << ' ' << (LL)round(yd) << '\n';
exit(0);
}
}
int main() {
//freopen(".in", "r", stdin);
//freopen(".out", "w", stdout);
cin >> A >> B >> C >> D;
if (B > D) swap(B, D);
double l = fabs(sqrt(A) - sqrt(D)) + Eps, r = sqrt(A) + sqrt(D) - Eps;
F(i, 1, 1000) {
double mid1 = l + (r - l) / 3.0, mid2 = r - (r - l) / 3.0;
if (check(mid1) < check(mid2)) r = mid2;
else l = mid1;
}
double true_mid = l;
l = fabs(sqrt(A) - sqrt(D)) + Eps, r = true_mid;
F(i, 1, 1000) {
double mid = (l + r) / 2.0;
if (check(mid) > B) l = mid;
else r = mid;
}
work(l);
l = true_mid, r = sqrt(A) + sqrt(D) - Eps;
F(i, 1, 1000) {
double mid = (l + r) / 2.0;
if (check(mid) < B) l = mid;
else r = mid;
}
work(l);
if (!f) assert(0);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3608kb
input:
36 5 10 41
output:
6 -1 2 3 1 4 5
result:
ok Answer is correct
Test #2:
score: 0
Accepted
time: 0ms
memory: 3672kb
input:
1 1 1 1
output:
1 -1 0 0 -1 1 0
result:
ok Answer is correct
Test #3:
score: 0
Accepted
time: 0ms
memory: 3648kb
input:
1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000
output:
1000000000 -1000000000 0 0 -1000000000 1000000000 0
result:
ok Answer is correct
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 3620kb
input:
4 10 8 2
output:
2 1 1 2 2 1 3
result:
wrong answer Squared distances are incorrect