Submission #1091046

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091046		BigBadBully	Portal (BOI24_portal)	C++17	1 / 100	53 ms	3408 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[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();
    
}

• Subtask 1: 1 / 1
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 29
• Subtask 5: 0 / 15
• Subtask 6: 0 / 35