#include "squad.h"
#include <algorithm>
#include <stdio.h>
using namespace std;
typedef long long lld;
struct coord {
lld x, y; int ix;
bool operator< (const coord& c) const {
if(x!=c.x) return x<c.x;
return y<c.y;
}
} AP[1001001], DP[1001001];
int N;
lld ccw(coord a, coord b, coord c){ // clockwise < 0
return (a.x*b.y+b.x*c.y+c.x*a.y) - (a.y*b.x+b.y*c.x+c.y*a.x);
}
void makehull(coord *ba, vector<int> &chk, int val, vector<coord> &cvx){
cvx.clear();
for(int i=0; i<N; i++){
int sz;
if(chk[ba[i].ix]==val) continue;
while(1){
sz=cvx.size();
if(sz<2) break;
if(ccw(cvx[sz-2], cvx[sz-1], ba[i]) < 0) break;
cvx.pop_back();
}
cvx.push_back(ba[i]);
}
}
void threehull(coord *ba, vector<coord> &cvx, vector<coord> &odd, vector<coord> &even){
vector<int> chk(N,0);
sort(ba, ba+N);
makehull(ba, chk, 1, cvx);
for(int i=cvx.size(); i--;){
if(i%2) chk[cvx[i].ix]=1;
else chk[cvx[i].ix]=2;
}
makehull(ba, chk, 1, odd);
makehull(ba, chk, 2, even);
}
vector<coord> Acv, Aov, Aev, Dcv, Dov, Dev;
void Init(int N_, vector<int> A, vector<int> D, vector<int> P){
N=N_;
for(int i=0; i<N; i++){
AP[i].ix=i, AP[i].x=A[i], AP[i].y=P[i];
DP[i].ix=i, DP[i].x=D[i], DP[i].y=P[i];
}
threehull(AP, Acv, Aov, Aev);
threehull(DP, Dcv, Dov, Dev);
}
int getfirst(lld A, lld B, vector<coord> &cvx){
if(cvx.size() == 1) return 0;
int mi=0, mx=cvx.size()-2, md;
while(mi<=mx){
md=(mi+mx)/2;
if(cvx[md].x*A + cvx[md].y*B < cvx[md+1].x*A + cvx[md+1].y*B) mi=md+1;
else mx=md-1;
}
return mi;
}
coord A1, A2, D1, D2;
lld BestSquad(int X, int Y){
int ix;
ix=getfirst(X, Y, Acv), A1=Acv[ix];
if(ix%2) ix=getfirst(X, Y, Aov), A2=Aov[ix];
else ix=getfirst(X, Y, Aev), A2=Aev[ix];
ix=getfirst(X, Y, Dcv), D1=Dcv[ix];
if(ix%2) ix=getfirst(X, Y, Dov), D2=Dov[ix];
else ix=getfirst(X, Y, Dev), D2=Dev[ix];
if(A1.ix != D1.ix) return (A1.x+D1.x)*X + (A1.y+D1.y)*Y;
return max((A2.x+D1.x)*X + (A2.y+D1.y)*Y, (A1.x+D2.x)*X + (A1.y+D2.y)*Y);
}
