Submission #1091079

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091079		BigBadBully	Portal (BOI24_portal)	C++17	1 / 100	59 ms	3260 KiB

Main

#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 / 1
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 29
• Subtask 5: 0 / 15
• Subtask 6: 0 / 35