oj.uz

Submission #1091045

# Submission time Handle Problem Language Result Execution time Memory
1091045 2024-09-19T15:20:50 Z BigBadBully Portal (BOI24_portal) C++17
1 / 100
 49 ms 3436 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[0].ff+dx1%dx2,v[1].ss-(dx1/dx2)*dy2};
     else
     result = {v[2].ff-dx2%dx1,v[1].ss+(dx2/dx1)*dy1};
    
    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[1],result,v[2]});
    }
    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[0],result,v[1]});
    }
}

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)
    {
        int gcdx = 0;
        for (int i = 1; i < n; i++)
        {
            if (v[i].ff == v[i-1].ff)
                continue;
            if (gcdx == 0)
                gcdx = v[i].ff-v[i-1].ff;
            else
                gcdx = __gcd(gcdx,v[i].ff-v[i-1].ff);
        }
        int gcdy = 0;
        for (int i = 0; i < n; i++)
        {
            swap(v[i].ff,v[i].ss);   
        }
        sort(v.begin(),v.end());
        for (int i = 1; i < n; i++)
        {
            if (v[i].ff == v[i-1].ff)
                continue;
            if (gcdy == 0)
                gcdy = v[i].ff-v[i-1].ff;
            else
                gcdy = __gcd(gcdx,v[i].ff-v[i-1].ff);
        }
        if (gcdy == 0 || gcdx == 0)
        {
            cout << -1 << endl;
            return;
        }
        cout << gcdx * gcdy << endl;
        return;
    }
  //  int sigma = 0;
    {
        if (a.ff<b.ff)
            swap(a,b);
        int dx = a.ff-b.ff;
        int dy = a.ss-b.ss;
        
        a = {a.ff%dx,a.ss-(a.ff/dx)*dy};
        b = {a.ff + dx, a.ss + dy};
        
    }

    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;
        
        a = {a.ff%dx,a.ss-(a.ff/dx)*dy};
        b = {a.ff + dx, a.ss + dy};
        
        /*if (a.ff > v[i].ff)
        {
        if (v[i].ss != a.ss-dy*(abs(a.ff-v[i].ff)/dx))
        {
            if (sigma == 0)
                sigma = abs(v[i].ss-a.ss);
            else
                sigma = __gcd(sigma,abs(v[i].ss-a.ss));
        }
        }
        else
        {
        if (v[i].ss != b.ss-dy*(abs(b.ff-v[i].ff)/dx))
        {
            if (sigma == 0)
                sigma = abs(v[i].ss-b.ss);
            else
                sigma = __gcd(sigma,abs(v[i].ss-b.ss));
        }
        }
        if (sigma)
            a.ss%=sigma;
        if (sigma)
            b.ss%=sigma;*/
    }
    /*if (sigma == 0)
    {
        cout << -1 << endl;
        return;
    }*/
    int vert = 0;
    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();
    
}

Compilation message

Main.cpp: In function 'void solve()':
Main.cpp:201:17: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
  201 |         else if (b.ff==v[i].ff)
      |                 ^
Main.cpp:193:12: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
  193 |         if (a.ff == v[i].ff)
      |            ^

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 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 436 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 436 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 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 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 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 436 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 436 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 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 348 KB Output is correct
20 Incorrect 0 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 1 ms 348 KB Output is correct
2 Incorrect 49 ms 3436 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 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 440 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 0 ms 352 KB Output is correct
10 Incorrect 0 ms 348 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 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 436 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 436 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 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 348 KB Output is correct
20 Incorrect 0 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 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 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 436 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 436 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 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 348 KB Output is correct
20 Incorrect 0 ms 348 KB Output isn't correct
21 Halted 0 ms 0 KB -