#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 && 0)
{
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);
for(ll i = 0; i < cln.size(); i++)
if(cmp(H, cek(cln[i], idx)))
H = cek(cln[i], idx);
kir[idx] = H;
return ;
// 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);
for(ll i = 0; i < cln.size(); i++)
if(cmp(cek(cln[i], idx), H))
H = cek(cln[i], idx);
kan[idx] = H;
return ;
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
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 'void cariL(ll)':
Main.cpp:59: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]
59 | for(ll i = 0; i < cln.size(); i++)
| ~~^~~~~~~~~~~~
Main.cpp: In function 'void cariR(ll)':
Main.cpp:98: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]
98 | for(ll i = 0; i < cln.size(); i++)
| ~~^~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:168: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]
168 | for(ll i = 0; i < isi.size(); i++)
| ~~^~~~~~~~~~~~
Main.cpp:166:8: warning: unused variable 'ada' [-Wunused-variable]
166 | ll ada = 0;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
154 ms |
1388 KB |
Output is correct |
| 2 |
Correct |
154 ms |
1260 KB |
Output is correct |
| 3 |
Correct |
155 ms |
1260 KB |
Output is correct |
| 4 |
Execution timed out |
2099 ms |
3256 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
492 KB |
Output is correct |
| 2 |
Correct |
8 ms |
620 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| 4 |
Correct |
7 ms |
492 KB |
Output is correct |
| 5 |
Correct |
1 ms |
364 KB |
Output is correct |
| 6 |
Correct |
7 ms |
492 KB |
Output is correct |
| 7 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
154 ms |
1388 KB |
Output is correct |
| 2 |
Correct |
154 ms |
1260 KB |
Output is correct |
| 3 |
Correct |
155 ms |
1260 KB |
Output is correct |
| 4 |
Execution timed out |
2099 ms |
3256 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
