oj.uz

Submission #1091079

# Submission time Handle Problem Language Result Execution time Memory
1091079 2024-09-19T17:11:36 Z BigBadBully Portal (BOI24_portal) C++17
1 / 100
 59 ms 3260 KB 
#include <bits/stdc++.h>
#define ff first
#define ss second
#define int long long
#define pii pair<int, int>
#define ff first
#define ss second
using namespace std;
const int inf = 1e17;
const int mod = 998244353;
const pii bad = {inf,inf};

vector<pii> milegcd(array<pii,3> v)
{
    //radi se po prvom
    sort(v.begin(),v.end());
    int dx1 = v[1].ff-v[0].ff,
    dx2 = v[2].ff - v[1].ff;
    if (dx1 == 0 || dx2==0)
    {
        vector<pii> finale(3);
        finale[0] = v[0];
        finale[1] = v[1];
        finale[2] = v[2];        
        return finale;
    }
    
    
    int dy1 = v[1].ss-v[0].ss,
    dy2 = v[2].ss-v[1].ss;
    pii result;
    if (dx1 > dx2)
     result = {v[1].ff-dx1%dx2,v[2].ss-(dx1/dx2)*dy1};
     else
     result = {v[1].ff+dx2%dx1,v[0].ss+(dx2/dx1)*dy2};

    if (dx1 <= dx2)
    {
        if (dx2%dx1 == 0)
        {
           
            vector<pii> finale(3);
            finale[0] = v[0];
            finale[1] = v[1];
            finale[2] = v[2];
        
            return finale;
            
        }
        return milegcd({v[0],result,v[1]});
    }
    else
    {
        if (dx1%dx2 == 0)
        {
           
            vector<pii> finale(3);
            finale[0] = v[0];
            finale[1] = v[1];
            finale[2] = v[2];
        
            return finale;
            
        }
        return milegcd({v[1],result,v[2]});
    }
}

void solve()
{
    int n;
    cin >> n;
    if (n<=2)
    {
        cout << -1 << endl;
        return;
    }
    
    vector<pii> v(n);
    for (int i = 0; i < n; i++)
        cin >> v[i].ff >> v[i].ss;
    sort(v.begin(),v.end());
    pii a = v[0],b = bad;
    for (int i = 1; i < n; i++)
        if (v[i].ff != a.ff)
        {
            b = v[i];
            break;
        }
    if (b == bad)
    {
        cout << -1 << endl;
        return;
    }

    int vert = 0;
    for (int i = 0; i < n; i++)
    {
        auto milorad = milegcd({a,b,v[i]});

        int dx1 = milorad[1].ff-milorad[0].ff;
        int dx2 = milorad[2].ff-milorad[1].ff;
        if (dx1 == 0 || dx2 == 0)
            continue;
        if (dx2 < dx1)
            a = milorad[1],b = milorad[2];
        else
            a = milorad[0],b = milorad[1];
        

        if (a.ff<b.ff)
            swap(a,b);
        
        int dx = a.ff-b.ff;
        int dy = a.ss-b.ss;
        if (dy == 0)
            vert = 1;
        a = {a.ff%dx,a.ss-(a.ff/dx)*dy};
        b = {a.ff + dx, a.ss + dy};
        
    
    }
    
    for (int i = 0; i < n; i++)
    {
        if (a.ff == v[i].ff)
        {
            if (abs(v[i].ss-a.ss) > 0)
            {
                if (vert == 0)
                    vert = abs(v[i].ss-a.ss);
                else
                    vert = __gcd(vert,abs(v[i].ss-a.ss));
            }
        }
        else if (b.ff==v[i].ff)
        {
            if (abs(v[i].ss-b.ss) > 0)
            {
                if (vert == 0)
                    vert = abs(v[i].ss-b.ss);
                else
                    vert = __gcd(vert,abs(v[i].ss-b.ss));
            }
        }
        else
        {
            int dy = abs(a.ss-b.ss);
            int dx = abs(a.ff-b.ff);
            if (v[i].ss != a.ss-dy*(abs(a.ff-v[i].ff)/dx))
            {
                if (vert == 0)
                    vert = abs(v[i].ss-a.ss);
                else
                    vert = __gcd(vert,abs(v[i].ss-a.ss));
            }
        }   
        
    }
    cout << vert*abs(a.ff-b.ff);

}
signed main()
{
 
    solve();
    
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Incorrect 1 ms 348 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 59 ms 3260 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 1 ms 344 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Incorrect 1 ms 348 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Incorrect 1 ms 348 KB Output isn't correct
21 Halted 0 ms 0 KB -