#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#define pii pair<int, int>
#define piii pair<int, pii>
#define pll pair<long long, long long>
#define plll pair<long long, pll>
#define tiii tuple<int, int, int>
#define tlll tuple<long long, long long, long long>
#define tiiii tuple<int, int, int, int>
#define tllll tuple<long long, long long, long long, long long>
#define ff first
#define ss second
#define ee ss.ff
#define rr ss.ss
//#define DEBUG
using namespace std;
const long long INF = (long long)8e18;
struct Frac
{
long long up, dn;
Frac(void) : up(0), dn(1) {}
Frac(long long x, long long y) : up(x), dn(y) { if(dn < 0) up = -up, dn = -dn; }
bool operator< (const Frac &ot) const { return up * ot.dn < ot.up * dn; }
};
struct Line
{
long long a, b;
Frac eval(Frac x) { return Frac(a * x.up + b * x.dn, x.dn); }
Frac cross(const Line &ot) const { return Frac(b - ot.b, ot.a - a); }
};
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, h; cin >> n >> h;
pii A[n]; for(auto &i : A) cin >> i.ff >> i.ss;
int N = (n - 3) / 2;
if(N == 0) { cout << 0; return 0; }
pair<Frac, Frac> ran[N];
vector<Line> ln;
for(int i = 1; i < n - 1; ++i)
{
if(i & 1)
{
Line x{A[i].ff, A[i].ss};
while(ln.size() >= 2 && x.cross(ln.back()) < x.cross(ln[(int)ln.size() - 2])) ln.pop_back();
ln.push_back(x);
}
else
{
Line x{A[i].ff, A[i].ss};
int s = 0, e = (int)ln.size();
while(s + 1 < e)
{
int mid = s + e >> 1;
Frac cr = ln[mid].cross(ln[mid - 1]);
if(x.eval(cr) < ln[mid].eval(cr)) s = mid;
else e = mid;
}
Frac tmp = x.cross(ln[s]);
ran[i / 2 - 1].ff = Frac(A[i].ff * tmp.up - (h - A[i].ss) * tmp.dn, tmp.up);
}
}
ln.clear();
for(int i = n - 1; i >= 1; --i)
{
if(i & 1)
{
Line x{-A[i].ff, A[i].ss};
while(ln.size() >= 2 && x.cross(ln.back()) < x.cross(ln[(int)ln.size() - 2])) ln.pop_back();
ln.push_back(x);
}
else
{
Line x{-A[i].ff, A[i].ss};
int s = 0, e = (int)ln.size();
while(s + 1 < e)
{
int mid = s + e >> 1;
Frac cr = ln[mid].cross(ln[mid - 1]);
if(x.eval(cr) < ln[mid].eval(cr)) s = mid;
else e = mid;
}
Frac tmp = x.cross(ln[s]);
ran[i / 2 - 1].ss = Frac(A[i].ff * tmp.up + (h - A[i].ss) * tmp.dn, tmp.up);
}
}
#ifdef DEBUG
cout << endl;
cout << "ran" << endl;
for(int i = 0; i < N; ++i)
{
cout << "{ " << ran[i].ff.up << " / " << ran[i].ff.dn << " }, ";
cout << "{ " << ran[i].ss.up << " / " << ran[i].ss.dn << " }\n";
}
cout << endl;
#endif
using pff = pair<Frac, Frac>;
sort(ran, ran + N, [](pff x, pff y){ return x.ss < y.ss; });
int ans = 1; Frac mn = ran[0].ss;
for(int i = 1; i < N; ++i)
{
if(mn < ran[i].ff)
++ans, mn = ran[i].ss;
}
cout << ans;
return 0;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:70:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
70 | int mid = s + e >> 1;
| ~~^~~
Main.cpp:96:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
96 | int mid = s + e >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
748 KB |
Output is correct |
| 2 |
Correct |
3 ms |
748 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
748 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
748 KB |
Output is correct |
| 2 |
Correct |
3 ms |
748 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
748 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
