QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#582308 | #9168. Square Locator | ucup-team4435# | AC ✓ | 1ms | 3736kb | C++20 | 3.6kb | 2024-09-22 16:00:20 | 2024-09-22 16:00:21 |
Judging History
answer
#pragma GCC optimize("Ofast")
#include "bits/stdc++.h"
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep1(i, n) for (int i = 1; i < (n); ++i)
#define rep1n(i, n) for (int i = 1; i <= (n); ++i)
#define repr(i, n) for (int i = (n) - 1; i >= 0; --i)
#define pb push_back
#define eb emplace_back
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define each(x, a) for (auto &x : a)
#define ar array
#define vec vector
#define range(i, n) rep(i, n)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using str = string;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vpi = vector<pair<int, int>>;
using vvi = vector<vi>;
int Bit(int mask, int b) { return (mask >> b) & 1; }
template<class T>
bool ckmin(T &a, const T &b) {
if (b < a) {
a = b;
return true;
}
return false;
}
template<class T>
bool ckmax(T &a, const T &b) {
if (b > a) {
a = b;
return true;
}
return false;
}
// [l, r)
template<typename T, typename F>
T FindFirstTrue(T l, T r, const F &predicat) {
--l;
while (r - l > 1) {
T mid = l + (r - l) / 2;
if (predicat(mid)) {
r = mid;
} else {
l = mid;
}
}
return r;
}
template<typename T, typename F>
T FindLastFalse(T l, T r, const F &predicat) {
return FindFirstTrue(l, r, predicat) - 1;
}
const ll INF = 2e18;
const int INFi = 1e9;
const int N = 2e5 + 5;
const int LG = 20;
ll my_sqrt(ll x) {
ll t = sqrtl(x);
while (t * t < x) t++;
while (t * t > x) t--;
return t;
}
pair<ll, ll> rot(pair<ll, ll> p) {
swap(p.first, p.second);
p.second *= -1;
return p;
}
void solve() {
// (s - x)^2 + y^2 = B
// (s - y)^2 + x^2 = D
// s^2 + x^2 + y^2 - 2sx = B
// s^2 + x^2 + y^2 - 2sy = D
// s^2 + x^2 + y^2 - 2sx = B
// x - y = (D - B) / (2s)
ll AO, BO, CO, DO; cin >> AO >> BO >> CO >> DO;
ll s = my_sqrt(AO);
ll B = BO;
ll D = DO;
ll diff = (D - B) / (2 * s); // (x - y)
assert(diff * (2 * s) == D - B);
// x = y + diff
// s^2 + (y+diff)^2 + y^2 - 2s(y+diff) = B
// 2y^2 + 2y(diff - s) + (s^2 + diff^2 - 2s * diff) - B = 0
ll a = 2;
ll b = 2 * (diff - s);
ll c = (s - diff) * (s - diff) - B;
b /= 2;
ll y = (-b + my_sqrt(b * b - a * c)) / a;
ll x = y + diff;
pair<ll, ll> Ap = {0, s};
pair<ll, ll> Bp = {-y, s - x};
auto sqr2 = [&] (pair<ll, ll> p) { return p.first * p.first + p.second * p.second; };
rep(t, 2) {
pair<ll, ll> Dp = {x, s - y};
if (t) Dp.first *= -1;
assert(sqr2(Ap) == AO);
assert(sqr2(Bp) == BO);
assert(sqr2(Dp) == DO);
pair<ll, ll> Cp = {Dp.first + Bp.first - Ap.first, Dp.second + Bp.second - Ap.second};
if (sqr2(Cp) != CO) continue;
pair<ll, ll> AB = {Bp.first - Ap.first, Bp.second - Ap.second};
pair<ll, ll> AD = {Dp.first - Ap.first, Dp.second - Ap.second};
if (rot(AB) != AD && rot(AD) != AB) continue;
cout << Ap.second << ' ' << Bp.first << ' ' << Bp.second << ' ' << Cp.first << ' ' << Cp.second << ' ' << Dp.first << ' ' << Dp.second << '\n';
return;
}
assert(0);
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout << setprecision(12) << fixed;
int t = 1;
// cin >> t;
rep(i, t) {
solve();
}
return 0;
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3632kb
input:
36 5 10 41
output:
6 -2 1 3 -1 5 4
result:
ok Answer is correct
Test #2:
score: 0
Accepted
time: 0ms
memory: 3608kb
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: 3696kb
input:
1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000
output:
1000000000 -1000000000 0 0 -1000000000 1000000000 0
result:
ok Answer is correct
Test #4:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
4 10 8 2
output:
2 -3 1 -2 -2 1 -1
result:
ok Answer is correct
Test #5:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
4 50 104 58
output:
2 -5 -5 2 -10 7 -3
result:
ok Answer is correct
Test #6:
score: 0
Accepted
time: 0ms
memory: 3564kb
input:
9 16 65 58
output:
3 0 -4 7 -4 7 3
result:
ok Answer is correct
Test #7:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
25 13 101 113
output:
5 2 -3 10 -1 8 7
result:
ok Answer is correct
Test #8:
score: 0
Accepted
time: 0ms
memory: 3736kb
input:
16 25 58 49
output:
4 -4 -3 3 -7 7 0
result:
ok Answer is correct
Test #9:
score: 0
Accepted
time: 0ms
memory: 3696kb
input:
374544 2235250 4453364 2592658
output:
612 -1205 -885 292 -2090 1497 -593
result:
ok Answer is correct
Test #10:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
126736 551200 1838608 1414144
output:
356 124 -732 1212 -608 1088 480
result:
ok Answer is correct
Test #11:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
6007401 6936277 5051405 4122529
output:
2451 -2599 426 -574 -2173 2025 -148
result:
ok Answer is correct
Test #12:
score: 0
Accepted
time: 0ms
memory: 3668kb
input:
2209 2536706 4875777 2341280
output:
47 -1435 691 -2079 -744 -644 -1388
result:
ok Answer is correct
Test #13:
score: 0
Accepted
time: 0ms
memory: 3544kb
input:
986962771600 2474826790757 5529645464114 4041781444957
output:
993460 -1210079 -1005254 788635 -2215333 1998714 -216619
result:
ok Answer is correct
Test #14:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
722790729241 782340801290 3904082690373 3844532618324
output:
850171 68947 -881809 1800927 -812862 1731980 919118
result:
ok Answer is correct
Test #15:
score: 0
Accepted
time: 0ms
memory: 3552kb
input:
3870332944 287487526720 654504136912 370886943136
output:
62212 77528 -530544 670284 -453016 592756 139740
result:
ok Answer is correct
Test #16:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
42230661001 2038831296200 3308981375377 1312380740178
output:
205501 -1201498 771514 -1767511 -429984 -566013 -995997
result:
ok Answer is correct
Test #17:
score: 0
Accepted
time: 0ms
memory: 3640kb
input:
132551656347532249 102473514386838101 439829344402853445 469907486363547593
output:
364076443 -144905351 -285439930 504611022 -430345281 649516373 219171092
result:
ok Answer is correct
Test #18:
score: 0
Accepted
time: 0ms
memory: 3692kb
input:
55636209407170681 109515374676898429 329424831462677605 275545666192949857
output:
235873291 -168654810 -284729573 351948054 -453384383 520602864 67218481
result:
ok Answer is correct
Test #19:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
466589422796014144 325095618166198298 43553814262839476 185047618892655322
output:
683073512 -483684563 301902073 -102513124 -181782490 381171439 199388949
result:
ok Answer is correct
Test #20:
score: 0
Accepted
time: 0ms
memory: 3672kb
input:
6909562468993284 229067899424048957 357610810027741258 135452473072685585
output:
83123778 -423763499 222468866 -563108587 -201294633 -139345088 -340639721
result:
ok Answer is correct
Test #21:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
5000019216542596 408275955794662066 885792080806957480 482516144228838010
output:
70710814 -163457821 -617703405 524956398 -781161226 688414219 -92747007
result:
ok Answer is correct
Test #22:
score: 0
Accepted
time: 0ms
memory: 3604kb
input:
1736111972222329 40264917317940640 105455671025820505 66926865680102194
output:
41666677 111335636 -166940988 319943301 -55605352 208607665 153002313
result:
ok Answer is correct
Test #23:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
255964325056888900 56517928013623933 645740568455742866 845186965499007833
output:
505929170 38979522 -234517643 779426335 -195538121 740446813 544908692
result:
ok Answer is correct
Test #24:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
477032252615296225 108870012374411737 333393233802837749 701555474043722237
output:
690675215 -324002404 -62389539 429062350 -386391943 753064754 366672811
result:
ok Answer is correct
Test #25:
score: 0
Accepted
time: 0ms
memory: 3552kb
input:
1299556716903225 355747388532580098 692024059544933421 337576227729256548
output:
36049365 -540431757 -252350757 -252031635 -792782514 288400122 -504382392
result:
ok Answer is correct
Test #26:
score: 0
Accepted
time: 0ms
memory: 3564kb
input:
65258206810145881 521153173952727205 930630862422604093 474735895280022769
output:
255456859 -653356447 -307048086 -90851502 -960404533 562504945 -397899588
result:
ok Answer is correct
Test #27:
score: 0
Accepted
time: 0ms
memory: 3604kb
input:
8131402216306944 151743259973886485 212869615963839370 69257758206259829
output:
90174288 -304122658 243418711 -457367081 -60703947 -153244423 -213948370
result:
ok Answer is correct
Extra Test:
score: 0
Extra Test Passed