QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#512757#8708. PortalAA_Surely#1 56ms10884kbC++233.5kb2024-08-10 15:40:012024-08-10 15:40:01

Judging History

This is the latest submission verdict.

  • [2024-08-10 15:40:01]
  • Judged
  • Verdict: 1
  • Time: 56ms
  • Memory: 10884kb
  • [2024-08-10 15:40:01]
  • Submitted

answer

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#define FOR(i, x, n) for(int i = x; i < n; i++)
#define F0R(i, n) FOR(i, 0, n)
#define ROF(i, x, n) for(int i = n - 1; i >= x; i--)
#define R0F(i, n) ROF(i, 0, n)

#define WTF cout << "WTF" << endl

#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define F first
#define S second
#define PB push_back
#define EP emplace_back

#define ALL(x) x.begin(), x.end()
#define RALL(x) x.rbegin(), x.rend()

using namespace std;

typedef long long LL;
typedef long double LD;

typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

typedef vector<int> VI;
typedef vector<LL> VLL;
typedef vector<PII> VPII;
typedef vector<PLL> VPLL;

typedef complex<LD> Point;

const int N = 2e5 + 7;
const int INF = 1e9 + 7;
const int LOG = 22;
const int A = 26;
const int SQ = 320;
const int MOD = 1e9 + 7;

LL n;
LL ns[N][2], dists[N][2];
map<LL, vector<LL>> x, y;
LL allx, ally;

int main() {
    IOS;
    
    cin >> n;
    if (n <= 2) {
        cout << -1 << endl;
        return 0;
    }

    F0R(i, n) {
        cin >> ns[i][0] >> ns[i][1];
        x[ ns[i][0] ].PB(ns[i][1]);
        y[ ns[i][1] ].PB(ns[i][0]);
    }

    FOR(i, 1, n) {
        allx = __gcd(allx, abs(ns[i][0] - ns[i - 1][0]));
        ally = __gcd(ally, abs(ns[i][1] - ns[i - 1][1]));
    }

    LL xs_gc = 0, ys_gc = 0;
    
    F0R(_, 3) {
        VPLL dists;
        FOR(i, 1, n) {
            PLL x;
            x.F = ns[i][0] - ns[0][0];
            x.S = ns[i][1] - ns[0][1];
            if (x.F != 0 && x.S != 0) {
                dists.PB(x);
            }

            else if (x.F == 0) {
                ys_gc = __gcd(ys_gc, abs(x.S));
            }

            else if (x.S == 0) {
                xs_gc = __gcd(xs_gc, abs(x.F));
            }
        }

        FOR(i, 2, dists.size()) {
            if (dists[i - 1].F < 0) {
                dists[i - 1].F *= -1;
                dists[i - 1].S *= -1;
            }

            if (dists[i].F < 0) {
                dists[i].F *= -1;
                dists[i].S *= -1;
            }

            int g = __gcd(dists[i].F, dists[i - 1].F);
            ys_gc = __gcd(1ll * ys_gc, abs(1ll * dists[i].S * dists[i - 1].F / g - 1ll * dists[i - 1].S * dists[i].F / g));

            if (dists[i - 1].S < 0) {
                dists[i - 1].S *= -1;
                dists[i - 1].F *= -1;
            }

            if (dists[i].S < 0) {
                dists[i].S *= -1;
                dists[i].F *= -1;
            }
            g = __gcd(dists[i].S, dists[i - 1].S);
            xs_gc = __gcd(1ll * xs_gc, abs(1ll * dists[i].F * dists[i - 1].S / g - 1ll * dists[i - 1].F * dists[i].S / g));
        }

        if (_ == 0) {
            FOR(i, 1, n) if (ns[i][0] != ns[0][0]) {
                swap(ns[i], ns[0]);
            }
        }
        if (_ == 2) {
            FOR(i, 1, n) if (ns[i][1] != ns[0][1]) {
                swap(ns[i], ns[0]);
            }
        }
    }

    for(auto &[a, b] : x) {
        LL gc = 0;
        FOR(i, 1, b.size())
            gc = __gcd(abs(b[i - 1] - b[i]), gc);
        ys_gc = __gcd(ys_gc, gc);
        if (b.size() >= 2) xs_gc = __gcd(xs_gc, allx);
    }

    for(auto &[a, b] : y) {
        LL gc = 0;
        FOR(i, 1, b.size())
            gc = __gcd(abs(b[i - 1] - b[i]), gc);
        xs_gc = __gcd(xs_gc, gc);
        if (b.size() >= 2) ys_gc = __gcd(ys_gc, allx);
    }

    if (ys_gc == 0 || xs_gc == 0) {
        cout << -1 << endl;
        return 0;
    }
    cout  << 1ll * ys_gc * xs_gc << endl;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 1
Accepted

Test #1:

score: 1
Accepted
time: 0ms
memory: 3600kb

input:

1
1 -1

output:

-1

result:

ok single line: '-1'

Test #2:

score: 1
Accepted
time: 0ms
memory: 3604kb

input:

2
-455833 -283524
427847 159281

output:

-1

result:

ok single line: '-1'

Test #3:

score: 1
Accepted
time: 0ms
memory: 3700kb

input:

2
52420 -46322
-192914 87067

output:

-1

result:

ok single line: '-1'

Test #4:

score: 1
Accepted
time: 0ms
memory: 3616kb

input:

2
52446 -20773
179773 174566

output:

-1

result:

ok single line: '-1'

Test #5:

score: 1
Accepted
time: 0ms
memory: 3596kb

input:

2
-229012 -260770
-174790 -69382

output:

-1

result:

ok single line: '-1'

Test #6:

score: 1
Accepted
time: 0ms
memory: 3592kb

input:

2
-127294 418312
211124 37002

output:

-1

result:

ok single line: '-1'

Test #7:

score: 1
Accepted
time: 0ms
memory: 3776kb

input:

2
-129173 516840
46821 -187136

output:

-1

result:

ok single line: '-1'

Test #8:

score: 1
Accepted
time: 0ms
memory: 3532kb

input:

2
-90088 -7423
234488 19625

output:

-1

result:

ok single line: '-1'

Test #9:

score: 1
Accepted
time: 0ms
memory: 3588kb

input:

2
-48105 256695
15135 -80585

output:

-1

result:

ok single line: '-1'

Test #10:

score: 1
Accepted
time: 0ms
memory: 3524kb

input:

2
-251318 79061
182792 -129183

output:

-1

result:

ok single line: '-1'

Test #11:

score: 1
Accepted
time: 0ms
memory: 3824kb

input:

2
784850 417677
-217245 -460999

output:

-1

result:

ok single line: '-1'

Test #12:

score: 1
Accepted
time: 0ms
memory: 3616kb

input:

2
31270 410692
713271 917276

output:

-1

result:

ok single line: '-1'

Test #13:

score: 1
Accepted
time: 0ms
memory: 3788kb

input:

1
230862 -785444

output:

-1

result:

ok single line: '-1'

Test #14:

score: 1
Accepted
time: 0ms
memory: 3600kb

input:

2
222814 -279784
-73657 59849

output:

-1

result:

ok single line: '-1'

Test #15:

score: 1
Accepted
time: 0ms
memory: 3464kb

input:

2
72171 -104186
201480 105502

output:

-1

result:

ok single line: '-1'

Test #16:

score: 1
Accepted
time: 0ms
memory: 3616kb

input:

2
-17727 -27151
69235 15029

output:

-1

result:

ok single line: '-1'

Test #17:

score: 1
Accepted
time: 0ms
memory: 3544kb

input:

2
-44049 96618
173806 -21489

output:

-1

result:

ok single line: '-1'

Test #18:

score: 1
Accepted
time: 0ms
memory: 3532kb

input:

2
-81268 -53452
329866 -163275

output:

-1

result:

ok single line: '-1'

Subtask #2:

score: 0
Wrong Answer

Dependency #1:

100%
Accepted

Test #19:

score: 10
Accepted
time: 1ms
memory: 5876kb

input:

3
1 1
1 3
3 2

output:

4

result:

ok single line: '4'

Test #20:

score: 0
Wrong Answer
time: 1ms
memory: 5532kb

input:

3
123741 -122828
207774 110184
-33847 97305

output:

-1

result:

wrong answer 1st lines differ - expected: '55218331445', found: '-1'

Subtask #3:

score: 0
Wrong Answer

Test #40:

score: 0
Wrong Answer
time: 56ms
memory: 10884kb

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:

1660

result:

wrong answer 1st lines differ - expected: '610880', found: '1660'

Subtask #4:

score: 0
Wrong Answer

Test #59:

score: 29
Accepted
time: 0ms
memory: 5636kb

input:

5
0 0
1 0
-1 0
0 1
0 -1

output:

1

result:

ok single line: '1'

Test #60:

score: 29
Accepted
time: 1ms
memory: 5808kb

input:

100
-30 -13
-22 -19
32 9
-18 -11
50 19
16 5
-50 -17
-46 -21
10 -1
-56 -19
2 -11
-24 -15
-4 -11
-8 -11
4 7
-8 -5
34 9
18 7
20 1
-12 -11
-30 -23
-42 -13
-24 -3
16 11
-16 -7
-24 -21
2 -9
28 11
6 -9
-22 -11
4 -7
28 7
-36 -15
-20 -21
4 11
-8 5
20 5
30 21
58 19
4 -1
-46 -19
-6 3
2 11
46 15
18 -1
-24 -7
-2...

output:

4

result:

ok single line: '4'

Test #61:

score: 29
Accepted
time: 1ms
memory: 5876kb

input:

100
66 27
38 -18
-39 -35
-4 9
-18 -24
24 26
17 6
-4 -26
-46 -6
52 1
17 -15
73 26
31 -10
-46 -27
-4 23
17 -29
-74 -37
-11 -39
-4 2
-11 10
3 -34
3 -41
-39 0
10 -14
31 -3
-18 -10
-25 -30
10 0
-53 -33
-18 -31
38 31
10 -35
24 5
52 22
-60 -32
-11 -32
17 13
-81 -36
3 29
-18 -45
-67 -31
45 23
31 -17
45 30
-...

output:

49

result:

ok single line: '49'

Test #62:

score: 0
Wrong Answer
time: 1ms
memory: 5684kb

input:

100
-36 37
19 49
31 -23
-16 61
-22 -65
40 -23
-48 1
-2 -41
-1 25
15 55
16 -41
-28 -29
30 19
48 19
8 -29
0 37
-8 -59
31 31
11 -47
12 19
15 1
36 -17
-49 -11
-6 73
-5 -23
-31 -11
-46 25
-33 -35
-44 -5
-42 -35
-21 -53
30 -35
1 49
46 -5
35 -29
10 49
-3 55
28 -5
25 -41
12 73
40 31
-54 -17
56 7
27 -17
-17 ...

output:

1

result:

wrong answer 1st lines differ - expected: '54', found: '1'

Subtask #5:

score: 0
Skipped

Dependency #2:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%