QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#533304#8708. Portalmakrav#11 1ms3944kbC++202.9kb2024-08-25 20:01:162024-08-25 20:01:17

Judging History

This is the latest submission verdict.

  • [2024-08-25 20:01:17]
  • Judged
  • Verdict: 11
  • Time: 1ms
  • Memory: 3944kb
  • [2024-08-25 20:01:16]
  • Submitted

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();
    }
}

Details

Tip: Click on the bar to expand more detailed information

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%