Submission #366722

#	Time	Username	Problem	Language	Result	Execution time	Memory
366722		faustaadp	Planine (COCI21_planine)	C++17	20 / 110	346 ms	63964 KiB

Main

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
const int NN = 1e6 + 5;
const int mo = 1e9 + 7;
const ld eps = 1e-9;
ll n, h;
ll x[NN], y[NN];
pair<ll, ll> kir[NN];
pair<ll, ll> kan[NN];
vector<ll> cln;
pair<ll, ll> cek(ll I, ll J)
{
    ll atas = x[I] * (y[J] - y[I]) + (x[J] - x[I]) * (h - y[I]);
    ll bawah = (y[J] - y[I]);
    pair<ll, ll> tmp = mp(atas, bawah);
    return tmp;
}
ll cmp(pair<ll, ll> aa, pair<ll, ll> bb)
{
    return aa.fi * bb.se < aa.se * bb.fi;
}
bool comp(pair<pair<ll, ll>, pair<ll, ll> > aa, pair<pair<ll, ll>, pair<ll, ll> > bb)
{
    return cmp(aa.fi, bb.fi);
}
void masuk(ll idx)
{
    while(cln.size() > 0 && y[cln.back()] <= y[idx])cln.pop_back();
    while(cln.size() > 1)
    {
        pair<ll, ll> A = mp(x[idx] - x[cln[cln.size() - 2]], y[idx] - y[cln[cln.size() - 2]]);
        pair<ll, ll> B = mp(x[cln[cln.size() - 1]] - x[cln[cln.size() - 2]], y[cln[cln.size() - 1]] - y[cln[cln.size() - 2]]);
        // cout << cmp(A, B) << "  " << cmp(B, A) << "@\n";
        // cout << A.fi << "/" << A.se << "  " << B.fi << "/" << B.se << "___\n"; 
        if(cmp(A, B))
            break;
        cln.pop_back();
    }
    // while(cln.size() > 0 && y[cln.back()] <= y[idx])cln.pop_back();
    cln.pb(idx);
}
void cetak()
{
    for(ll i = 0; i < cln.size(); i++)
        cout << cln[i] << ", ";
    cout << "\n";
}
void cariL(ll idx)
{
    ll L = 0, R = cln.size() - 1;
    pair<ll, ll> H;
    H = cek(cln[0], idx);
    // cout << " cari " << L << " " << R << "\n"; 
    while(L <= R)
    {
        ll C1 = L + (R - L) / 3;
        ll C2 = R - (R - L) / 3;
        pair<ll, ll> CC1 = cek(cln[C1], idx);
        pair<ll, ll> CC2 = cek(cln[C2], idx);
        // cout << C1 << ", " << C2 << "___\n";
        // cout << CC1.fi << "/" << CC1.se << "  " << CC2.fi << " " << << "___\n";
        if(y[cln[C2]] <= y[idx])
            R = C2 - 1;
        else
        if(cmp(CC1, CC2))
        {
            if(cmp(H, CC2))
                H = CC2;
            L = C1 + 1;
        }
        else
        {
            if(cmp(H, CC1))
                H = CC1;
            R = C2 - 1;
        }
    }
    // cout << H.fi << "/" << H.se << "\n";
    kir[idx] = H; 
}
void cariR(ll idx)
{
    ll L = 0, R = cln.size() - 1;
    // cout << " cari " << L << " " << R << "  " << idx << "\n"; 
    pair<ll, ll> H;
    H = cek(cln[0], idx);
    while(L <= R)
    {
        ll C1 = L + (R - L) / 3;
        ll C2 = R - (R - L) / 3;
        pair<ll, ll> CC1 = cek(cln[C1], idx);
        pair<ll, ll> CC2 = cek(cln[C2], idx);
        // cout << C1 << " " << C2 << "\n";
        // cout << CC1.fi << "/" << CC1.se << "  " << CC2.fi << "/" << CC2.se << "___\n";
        if(y[cln[C2]] <= y[idx])
            R = C2 - 1;
        else
        if(cmp(CC1, CC2))
        {
            if(cmp(CC1, H))
                H = CC1;
            R = C2 - 1;
        }
        else
        {
            if(cmp(CC2, H))
                H = CC2;
            L = C1 + 1;
        }
    }
    // cout << H.fi << "/" << H.se << " hai\n";
    kan[idx] = H; 
}
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> h;
    for(ll i = 1; i <= n; i++)
        cin >> x[i] >> y[i];
    vector<pair<pair<ll, ll>, pair<ll, ll> > > isi;
    for(ll i = 1; i <= n; i++)
    {
        if((i % 2 == 1) && (i > 1) && (i < n))
        {
            cariL(i);
        }
        masuk(i);
        // cetak();
    }
    cln.clear();
    for(ll i = n; i >= 1; i--)
    {
        if((i % 2 == 1) && (i > 1) && (i < n))
        {
            cariR(i);
        }
        masuk(i);
        // cetak();
    }
    for(ll i = 1; i <= n; i++)
    {
        if((i % 2 == 1) && (i > 1) && (i < n))
        {
            // cout << kir[i].fi << "/" << kir[i].se << "  " << kan[i].fi << "/" << kan[i].se << "_\n";
            isi.pb(mp(kir[i], kan[i]));
        }
    }
    ll has = 0;
    sort(isi.begin(), isi.end(), comp);
    ll ada = 0;
    pair<ll, ll> mii = mp(-1, -1);
    for(ll i = 0; i < isi.size(); i++)
    {
        // cout << isi[i].fi.fi << " " << isi[i].fi.se << " " << isi[i].se.fi << " " << isi[i].se.se << "\n";
        if(i == 0 || cmp(mii, isi[i].fi))
        {
            mii = isi[i].se;
            has++;
        }
        if(cmp(isi[i].se, mii))
            mii = isi[i].se;
    }
    cout << has << "\n";
}
    

Compilation message (stderr)

Main.cpp: In function 'void cetak()':
Main.cpp:50:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     for(ll i = 0; i < cln.size(); i++)
      |                   ~~^~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:158:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<std::pair<long long int, long long int>, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  158 |     for(ll i = 0; i < isi.size(); i++)
      |                   ~~^~~~~~~~~~~~
Main.cpp:156:8: warning: unused variable 'ada' [-Wunused-variable]
  156 |     ll ada = 0;
      |        ^~~

• Subtask 1: 20 / 20
• Subtask 2: 0 / 30
• Subtask 3: 0 / 60