38 lines
741 B
C++
38 lines
741 B
C++
namespace LC
|
|
{
|
|
|
|
vll line;
|
|
int getline(ll c)
|
|
{
|
|
int k = 0, st = 20;
|
|
while(st+1)
|
|
{
|
|
int now = k+(1<<st); st--;
|
|
if(now >= line.size()) continue;
|
|
|
|
if(line[now].fi*c+line[now].se < line[now-1].fi*c+line[now-1].se) k = now;
|
|
}
|
|
return k;
|
|
}
|
|
void pushline(pll C)
|
|
{
|
|
while(line.size() >= 2)
|
|
{
|
|
pll A = line[line.size()-2];
|
|
pll B = line.back();
|
|
|
|
A = {A.fi-C.fi, A.se-C.se};
|
|
B = {B.fi-C.fi, B.se-C.se};
|
|
A.se = -A.se; B.se = -B.se;
|
|
|
|
if(A.fi<0) A = {-A.fi, -A.se};
|
|
if(B.fi<0) B = {-B.fi, -B.se};
|
|
|
|
|
|
if(A.se*B.fi >= B.se*A.fi) line.pop_back();
|
|
else break;
|
|
}
|
|
line.pb(C);
|
|
}
|
|
|
|
} // namespace LC
|