QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#533304 | #8708. Portal | makrav# | 11 | 1ms | 3944kb | C++20 | 2.9kb | 2024-08-25 20:01:16 | 2024-08-25 20:01:17 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll
#define pb push_back
int gcd(int x, int y) {
x = abs(x); y = abs(y);
while (x) {
y %= x;
swap(x, y);
}
return y;
}
int lcm(int x, int y) {
return abs(x) * abs(y) / gcd(x, y);
}
void solve() {
int n; cin >> n;
vector<pair<int, int>> a(n);
for (int i = 0; i < n; i++) cin >> a[i].first >> a[i].second;
vector<pair<int, int>> v;
for (int i = 1; i < n; i++) {
v.pb({a[i].first - a[0].first, a[i].second - a[0].second});
}
bool line = true;
for (int i = 2; i < n; i++) {
if ((a[i].first - a[0].first) * (a[1].second - a[0].second) - (a[i].second - a[0].second) * (a[1].first - a[0].first) != 0) line = false;
}
if (line) {
cout << "-1\n";
return;
}
vector<pair<int, int>> newv = {v[0]};
for (int i = 1; i < n - 1; i++) {
if (v[i].first * v[0].second - v[i].second * v[0].first != 0) {
newv.pb(v[i]);
for (int j = 1; j < n; j++) {
if (j != i) newv.pb(v[j]);
}
break;
}
}
swap(v, newv);
int cdx, cdy;
if (v[0].first == 0) {
cdy = abs(v[0].second);
} else if (v[1].first == 0) {
cdy = abs(v[1].second);
} else {
cdy = abs(v[0].second * (v[1].first / gcd(v[1].first, v[0].first)) - v[1].second * (v[0].first / gcd(v[1].first, v[0].first)));
}
if (v[0].second == 0) {
cdx = abs(v[0].first);
} else if (v[1].second == 0) {
cdx = abs(v[1].first);
} else {
cdx = abs(v[0].first * (v[1].second / gcd(v[1].second, v[0].second)) - v[1].first * (v[0].second / gcd(v[1].second, v[0].second)));
}
int drx = gcd(v[0].first, v[1].first), dry = gcd(v[1].second, v[0].second);
//assert(cdx == drx);
for (int i = 2; i < n - 1; i++) {
int ndrx = cdx * dry / cdy;
int ndry = cdy * drx / cdx;
int HUY = lcm(v[i].second, dry) / v[i].second, HUY2 = lcm(v[i].second, dry) / dry;
int lolx = v[i].first * HUY - ndrx * HUY2;
HUY = lcm(v[i].first, drx) / v[i].first; HUY2 = lcm(v[i].first, drx) / drx;
int loly = v[i].second * HUY - ndry * HUY2;
cdx = gcd(cdx, lolx);
cdy = gcd(cdy, loly);
drx = gcd(drx, v[i].first);
dry = gcd(dry, v[i].second);
// ndrx - delta of x values of neighbour rows (by y)
// ndry - delta of y values of neighbour columns
}
//cout << drx * dry << '\n';
cout << cdx * dry << '\n';
}
signed main() {
int tt = 1;
#ifdef LOCAL
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
cin >> tt;
#else
ios::sync_with_stdio(false); cin.tie(0);
#endif
while (tt--) {
solve();
}
}
详细
Subtask #1:
score: 1
Accepted
Test #1:
score: 1
Accepted
time: 0ms
memory: 3748kb
input:
1 1 -1
output:
-1
result:
ok single line: '-1'
Test #2:
score: 1
Accepted
time: 0ms
memory: 3752kb
input:
2 -455833 -283524 427847 159281
output:
-1
result:
ok single line: '-1'
Test #3:
score: 1
Accepted
time: 0ms
memory: 3760kb
input:
2 52420 -46322 -192914 87067
output:
-1
result:
ok single line: '-1'
Test #4:
score: 1
Accepted
time: 0ms
memory: 3780kb
input:
2 52446 -20773 179773 174566
output:
-1
result:
ok single line: '-1'
Test #5:
score: 1
Accepted
time: 0ms
memory: 3616kb
input:
2 -229012 -260770 -174790 -69382
output:
-1
result:
ok single line: '-1'
Test #6:
score: 1
Accepted
time: 0ms
memory: 3528kb
input:
2 -127294 418312 211124 37002
output:
-1
result:
ok single line: '-1'
Test #7:
score: 1
Accepted
time: 0ms
memory: 3548kb
input:
2 -129173 516840 46821 -187136
output:
-1
result:
ok single line: '-1'
Test #8:
score: 1
Accepted
time: 0ms
memory: 3784kb
input:
2 -90088 -7423 234488 19625
output:
-1
result:
ok single line: '-1'
Test #9:
score: 1
Accepted
time: 0ms
memory: 3596kb
input:
2 -48105 256695 15135 -80585
output:
-1
result:
ok single line: '-1'
Test #10:
score: 1
Accepted
time: 0ms
memory: 3556kb
input:
2 -251318 79061 182792 -129183
output:
-1
result:
ok single line: '-1'
Test #11:
score: 1
Accepted
time: 0ms
memory: 3752kb
input:
2 784850 417677 -217245 -460999
output:
-1
result:
ok single line: '-1'
Test #12:
score: 1
Accepted
time: 0ms
memory: 3596kb
input:
2 31270 410692 713271 917276
output:
-1
result:
ok single line: '-1'
Test #13:
score: 1
Accepted
time: 0ms
memory: 3596kb
input:
1 230862 -785444
output:
-1
result:
ok single line: '-1'
Test #14:
score: 1
Accepted
time: 0ms
memory: 3616kb
input:
2 222814 -279784 -73657 59849
output:
-1
result:
ok single line: '-1'
Test #15:
score: 1
Accepted
time: 0ms
memory: 3828kb
input:
2 72171 -104186 201480 105502
output:
-1
result:
ok single line: '-1'
Test #16:
score: 1
Accepted
time: 0ms
memory: 3484kb
input:
2 -17727 -27151 69235 15029
output:
-1
result:
ok single line: '-1'
Test #17:
score: 1
Accepted
time: 0ms
memory: 3548kb
input:
2 -44049 96618 173806 -21489
output:
-1
result:
ok single line: '-1'
Test #18:
score: 1
Accepted
time: 0ms
memory: 3544kb
input:
2 -81268 -53452 329866 -163275
output:
-1
result:
ok single line: '-1'
Subtask #2:
score: 10
Accepted
Dependency #1:
100%
Accepted
Test #19:
score: 10
Accepted
time: 0ms
memory: 3560kb
input:
3 1 1 1 3 3 2
output:
4
result:
ok single line: '4'
Test #20:
score: 10
Accepted
time: 0ms
memory: 3608kb
input:
3 123741 -122828 207774 110184 -33847 97305
output:
55218331445
result:
ok single line: '55218331445'
Test #21:
score: 10
Accepted
time: 0ms
memory: 3784kb
input:
3 -66381 27989 200580 40286 300930 -238824
output:
75745488660
result:
ok single line: '75745488660'
Test #22:
score: 10
Accepted
time: 0ms
memory: 3536kb
input:
3 -212612 305891 -228367 216399 56731 149417
output:
26569291626
result:
ok single line: '26569291626'
Test #23:
score: 10
Accepted
time: 0ms
memory: 3524kb
input:
3 58252 388020 34720 -409605 79321 85296
output:
23928862293
result:
ok single line: '23928862293'
Test #24:
score: 10
Accepted
time: 0ms
memory: 3476kb
input:
3 19556 -29968 -52219 72940 153159 -166846
output:
3924399074
result:
ok single line: '3924399074'
Test #25:
score: 10
Accepted
time: 0ms
memory: 3544kb
input:
3 201002 729262 -242878 -881858 183722 666542
output:
-1
result:
ok single line: '-1'
Test #26:
score: 10
Accepted
time: 0ms
memory: 3620kb
input:
3 -425251 245407 695099 -401393 18815 -10961
output:
-1
result:
ok single line: '-1'
Test #27:
score: 10
Accepted
time: 0ms
memory: 3576kb
input:
3 -74800 392658 -48320 253638 -13280 69678
output:
-1
result:
ok single line: '-1'
Test #28:
score: 10
Accepted
time: 0ms
memory: 3780kb
input:
3 376570 -515419 -67488 -129024 -72636 -138852
output:
6353363484
result:
ok single line: '6353363484'
Test #29:
score: 10
Accepted
time: 0ms
memory: 3528kb
input:
3 -365409 -46168 130463 -388367 -745599 -94238
output:
153937204850
result:
ok single line: '153937204850'
Test #30:
score: 10
Accepted
time: 0ms
memory: 3608kb
input:
3 4925 198059 583262 -155627 573812 -153107
output:
1884923460
result:
ok single line: '1884923460'
Test #31:
score: 10
Accepted
time: 0ms
memory: 3816kb
input:
1 -785465 814199
output:
-1
result:
ok single line: '-1'
Test #32:
score: 10
Accepted
time: 0ms
memory: 3480kb
input:
3 107518 -84340 137659 -15241 359437 347683
output:
4385745738
result:
ok single line: '4385745738'
Test #33:
score: 10
Accepted
time: 0ms
memory: 3480kb
input:
3 -203959 7059 -34097 -218222 96949 -293501
output:
16735132428
result:
ok single line: '16735132428'
Test #34:
score: 10
Accepted
time: 0ms
memory: 3808kb
input:
3 18005 283441 106422 -61165 137635 -175433
output:
652953322
result:
ok single line: '652953322'
Test #35:
score: 10
Accepted
time: 0ms
memory: 3780kb
input:
3 -233201 -63834 105532 -12105 337350 41702
output:
6234493209
result:
ok single line: '6234493209'
Test #36:
score: 10
Accepted
time: 0ms
memory: 3524kb
input:
3 36748 -26399 119775 -223323 224245 -89339
output:
31696939848
result:
ok single line: '31696939848'
Test #37:
score: 10
Accepted
time: 0ms
memory: 3584kb
input:
3 1000000 -110976 -1000000 -1000000 715820 1000000
output:
2474594840320
result:
ok single line: '2474594840320'
Test #38:
score: 10
Accepted
time: 0ms
memory: 3480kb
input:
3 48920 1000000 1000000 -680401 -1000000 -1000000
output:
3664766216920
result:
ok single line: '3664766216920'
Test #39:
score: 10
Accepted
time: 0ms
memory: 3544kb
input:
3 196198 1000000 1000000 -520790 -1000000 -1000000
output:
3426769956420
result:
ok single line: '3426769956420'
Subtask #3:
score: 0
Runtime Error
Test #40:
score: 0
Runtime Error
input:
99840 -359536 735499 -710626 400619 -468266 -282389 -192706 43659 204034 -543669 -100576 -749013 -118006 -283125 -341276 405771 560934 835595 -923936 506603 239724 956299 -680746 -737237 286204 982795 -847576 -282389 -949666 986475 996684 -429589 672984 -133717 140954 696491 -879116 -442837 985064 7...
output:
result:
Subtask #4:
score: 0
Runtime Error
Test #59:
score: 0
Runtime Error
input:
5 0 0 1 0 -1 0 0 1 0 -1
output:
result:
Subtask #5:
score: 0
Wrong Answer
Dependency #2:
100%
Accepted
Test #97:
score: 0
Wrong Answer
time: 1ms
memory: 3944kb
input:
2000 -141033 500883 -457875 317099 570107 -451327 -258775 83073 -48988 -181339 184246 148615 322139 -358663 205746 -28713 -246818 493221 315791 -439181 243789 -493721 -152335 -120605 -290252 397465 359491 -136925 321141 -96245 -410156 465995 192919 -87583 464977 -450703 99537 240803 -279989 264903 -...
output:
2
result:
wrong answer 1st lines differ - expected: '19966', found: '2'
Subtask #6:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
0%