#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define pb push_back
#define mp make_pair
#define PI ( acos(-1.0) )
#define FOR(i,a,b) for(i=a ; i<=b ; i++)
#define DBG printf("Hi\n")
#define i64 long long int
#define eps (1e-8)
#define xx first
#define yy second
#define ln 17
#define off 2
#define SZ(z) ((int)z.size())
#define MEM(a,x) memset(a,x,sizeof(a))
#define FastIO ios_base::sync_with_stdio(false); cin.tie(NULL)
using namespace __gnu_pbds;
using namespace std ;
typedef tree< i64, null_type, less<i64>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
#define IN freopen("262144.in","r",stdin)
#define OUT freopen("262144.out","w",stdout)
#include<squad.h>
#define maxn 300005
#define INF 1000000000
#define mod 998244353LL
#define log 60
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long int T ;
struct PT {
T x , y ;
PT() {}
PT(T x_,T y_) {x=x_,y=y_;}
PT operator + (const PT &p) { return {x+p.x,y+p.y} ;}
PT operator - (const PT &p) { return {x-p.x,y-p.y} ;}
PT operator * (const T &t) { return {x*t,y*t} ;}
T operator * (const PT &p) { return x*p.x + y*p.y ; }
T operator ^ (const PT &p) { return x*p.y - y*p.x ;}
bool operator==( const PT &p )const { return ((x==p.x) && (y==p.y)) ; }
bool operator!=( const PT &p )const { return ((x!=p.x) || (y!=p.y)) ; }
bool operator<(const PT &p) { return make_pair(x,y) < make_pair(p.x,p.y) ; }
};
double abs( PT p ){ return sqrt( p*p ) ; }
ostream& operator<<(ostream& os , PT p)
{
os<<setprecision(10) ;
return os<<"("<<p.x<<","<<p.y<<")" ;
}
T orient( PT a , PT b, PT c )
{
//if ac is to the left of ab , it returns 1
//if ac is in the same line as ab, it returns 0
//if ac is to the right of ab, it returns -1
return (b-a)^(c-a) ;
}
//collected form tfg's code
bool comp(PT a, PT b){
if((a.x > 0 || (a.x==0 && a.y>0) ) && (b.x < 0 || (b.x==0 && b.y<0))) return 1;
if((b.x > 0 || (b.x==0 && b.y>0) ) && (a.x < 0 || (a.x==0 && a.y<0))) return 0;
long long R = a^b;
if(R) return R > 0;
return a*a < b*b;
}
vector<PT> minkowskiSum(vector<PT> &a, vector<PT> &b){
if(a.empty() || b.empty()) return std::vector<PT>(0);
vector<PT> ret;
if(min(a.size(), b.size()) < 2){
for(int i = 0; i < (int) a.size(); i++) {
for(int j = 0; j < (int) b.size(); j++) {
ret.push_back(a[i]+b[j]);
}
}
}
ret.push_back(a[0]+b[0]);
PT p = ret.back();
int pa = 0, pb = 0;
while(pa + pb + 1 < a.size()+b.size()){
if(pb == (int) b.size() || (pa < (int) a.size() && comp((a[(pa+1)%a.size()]-a[pa]),(b[(pb+1)%b.size()]-b[pb]))))
p = p + (a[(pa+1)%a.size()]-a[pa]), pa++;
else p = p + (b[(pb+1)%b.size()]-b[pb]), pb++;
while(ret.size() >= 2 && ((p-ret.back())^(p-ret[(int)ret.size()-2])) == 0) {
ret.pop_back();
}
ret.push_back(p);
}
return ret;
}
//Collected from our template library
PT dir;
bool half(PT p){
return (dir^p) < 0 ||
( (dir^p) == 0 && (dir*p) > 0);
}
bool polarComp(PT p, PT q) {
return make_tuple(half(p), 0)
< make_tuple(half(q), (p^q));
}
void process(vector<PT> &P) {
int mnid = 0;
for (int i=0; i<P.size(); i++)
if (P[i] < P[mnid])
mnid = i;
rotate(P.begin(), P.begin()+mnid, P.end());
}
vector<PT> MinkowskiSum(vector<PT>A, vector<PT>B){
process(A); process(B);
int n = A.size(), m = B.size();
vector<PT> P(n), Q(m);
for(int i=0; i<n; i++) P[i] = A[(i+1)%n] - A[i];
for(int i=0; i<m; i++) Q[i] = B[(i+1)%m] - B[i];
dir = PT(0, -1);
vector<PT> C(n+m+1);
merge(P.begin(), P.end(), Q.begin(), Q.end(),
C.begin()+1, polarComp);
C[0] = A[0] + B[0];
for(int i=1; i<C.size(); i++) C[i]=C[i]+C[i-1];
C.pop_back();
return C;
}
vector<PT> monotone_chain (vector <PT> &p, bool fl=false) {
if(p.size()==0) return vector<PT>(0) ;
vector<PT> hull ;
vector <PT> L, U;
sort (p.begin() , p.end()) ;
for(int i = 0 ; i < p.size() ; i++) {
while(L.size() >= 2 and orient(L[L.size()-2] , L.back() , p[i]) <= 0) {
L.pop_back() ;
}
L.push_back(p[i]) ;
}
for(int i = (int)p.size()-1 ; i >= 0 ; i--) {
while(U.size() >= 2 and orient(U[U.size()-2] , U.back() , p[i]) <= 0) {
U.pop_back() ;
}
U.push_back(p[i]) ;
}
for(int i = 0 ; i < L.size() ; i++) hull.push_back(L[i]) ;
if (L.back()!=U[0]) hull.push_back(U[0]) ;
for(int i = 1 ; i + 1 < U.size() ; i++) hull.push_back(U[i]) ;
if (U.back()!=L[0]) hull.push_back(U.back()) ;
if( hull.size() == 2 && hull[0] == hull[1] ) hull.pop_back() ;
return hull ;
}
struct data{
int a , d , p ;
bool operator<(data other){ return a-d < other.a-other.d ; }
}ara[maxn];
vector<PT> getHull(int b, int e)
{
if(b>=e) return vector<PT>(0) ;
int m = (b+e)/2 ;
vector<PT> p1 = getHull(b,m) , p2 = getHull(m+1,e) ;
vector<PT> p3 , p4 ;
for(int i=b ; i<=m ; i++)
{
p3.pb( PT(ara[i].d,ara[i].p) ) ;
}
for(int i=m+1 ; i<=e ; i++)
{
p4.pb( PT(ara[i].a,ara[i].p) ) ;
}
p3 = monotone_chain(p3) ; p4 = monotone_chain(p4) ;
vector<PT> p = MinkowskiSum(p3,p4) ;
for(int i=0 ; i<p1.size() ; i++) p.pb(p1[i]) ;
for(int i=0 ; i<p2.size() ; i++) p.pb(p2[i]) ;
p = monotone_chain(p) ;
return p ;
}
vector<PT> hull ;
void Init(vector<int> a , vector<int> d , vector<int> p)
{
int n = a.size() ;
for(int i=1 ; i<=n ; i++)
{
ara[i].a = a[i-1] ;
ara[i].d = d[i-1] ;
ara[i].p = p[i-1] ;
}
sort(ara+1,ara+n+1) ;
vector<PT> h = getHull(1,n) ;
sort(h.begin(),h.end()) ;
hull = h ;
// for(auto p: hull) cout<<p<<endl ;
// return ;
int idx = 0 ;
for(int i=0 ; i<hull.size() ; i++)
{
while( idx>0 && hull[idx-1].y <= hull[i].y ) idx-- ;
hull[idx] = hull[i] ;
idx++ ;
}
// printf("%d\n",idx) ;
hull.erase( hull.begin()+idx , hull.end() ) ;
}
i64 BestSquad(i64 x, i64 y)
{
int l = 0 , r = (int)hull.size() - 1 ;
PT p(x,y) ;
while( l+3 <= r )
{
// printf("-- %d %d\n",l,r) ;
int mid1 = l + (r-l)/3 , mid2 = l + (2*(r-l))/3 ;
if( hull[mid1]*p < hull[mid2]*p ) l = mid1 ;
else r = mid2 ;
}
i64 ans = hull[l]*p ;
for(int i=l ; i<=r ; i++) ans = max( ans , hull[i]*p ) ;
return ans ;
}
vector<PT> getPoints(int n)
{
vector<PT> points ;
for(int i=0 ; i<n ; i++)
{
PT p ;
p.x = rng()%100 ;
p.y = rng()%100 ;
points.pb(p) ;
}
return points ;
}
/*
int main()
{
int n = 1000 ;
vector<int> a , d , p ;
for(int i=1 ; i<=n ; i++)
{
int m = 1000000000 ;
a.pb( rng()%m + 1 ) ;
d.pb( rng()%m + 1 ) ;
p.pb( rng()%m + 1 ) ;
}
Init(a,d,p) ;
for(auto p: hull) cout<<p<<endl ;
int cnt = 50 ;
while(cnt--)
{
int x , y ;
x = rng()%10000 + 1 ; y = rng()%10000 + 1 ;
printf("%d %d\n",x,y) ;
//scanf("%d %d",&x,&y) ;
i64 ansbrute = 0 ;
for(int i=0 ; i<n ; i++)
{
for(int j=0 ; j<n ; j++)
{
if(i==j) continue ;
ansbrute = max( ansbrute , 1LL*x*(a[i]+d[j]) + 1LL*y*(p[i]+p[j]) ) ;
}
}
i64 mainans = 0 ;
for(int i=0 ; i<hull.size() ; i++)
{
mainans = max( 1LL*mainans , 1LL*hull[i].x*x + 1LL*hull[i].y*y ) ;
}
printf("brute: %lld main: %lld best: %lld\n",ansbrute,mainans,BestSquad(x,y)) ;
if( ansbrute != BestSquad(x,y) )
{
printf("------------\n") ;
return 0 ;
}
}
vector<PT> p1 = getPoints(n) , p2 = getPoints(n) ;
p1 = monotone_chain(p1) ; p2 = monotone_chain(p2) ;
p2 = p1 ;
vector<PT> p3 ;
vector<PT> p5 , p4 ;
for(int i=0 ; i<p1.size() ; i++)
{
for(int j=0 ; j<p2.size() ; j++) p5.pb( p1[i]+p2[j] ) ;
}
p5 = monotone_chain(p5) ;
p3 = MinkowskiSum(p1,p2) ; //our template code
p4 = minkowskiSum(p1,p2) ; //tfg's code
p3 = monotone_chain(p3) ;
p4 = monotone_chain(p4) ;
for(auto p:p3) cout<<p<<endl ;
cout<<endl<<endl ;
for(auto p:p4) cout<<p<<endl ;
cout<<endl<<endl ;
sort(p3.begin(),p3.end()) ;
sort(p4.begin(),p4.end()) ;
if(p3==p4) cout<<"yes"<<endl ;
else cout<<"no"<<endl ;
cout<<(p3==p4)<<endl ;
for(auto p:p5) cout<<p<<endl ;
return 0 ;
}
*/
Compilation message
squad.cpp: In function 'std::vector<PT> minkowskiSum(std::vector<PT>&, std::vector<PT>&)':
squad.cpp:91:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<PT>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
91 | while(pa + pb + 1 < a.size()+b.size()){
| ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
squad.cpp: In function 'void process(std::vector<PT>&)':
squad.cpp:116:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<PT>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
116 | for (int i=0; i<P.size(); i++)
| ~^~~~~~~~~
squad.cpp: In function 'std::vector<PT> MinkowskiSum(std::vector<PT>, std::vector<PT>)':
squad.cpp:132:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<PT>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
132 | for(int i=1; i<C.size(); i++) C[i]=C[i]+C[i-1];
| ~^~~~~~~~~
squad.cpp: In function 'std::vector<PT> monotone_chain(std::vector<PT>&, bool)':
squad.cpp:144:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<PT>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
144 | for(int i = 0 ; i < p.size() ; i++) {
| ~~^~~~~~~~~~
squad.cpp:158:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<PT>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
158 | for(int i = 0 ; i < L.size() ; i++) hull.push_back(L[i]) ;
| ~~^~~~~~~~~~
squad.cpp:160:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<PT>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
160 | for(int i = 1 ; i + 1 < U.size() ; i++) hull.push_back(U[i]) ;
| ~~~~~~^~~~~~~~~~
squad.cpp: In function 'std::vector<PT> getHull(int, int)':
squad.cpp:188:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<PT>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
188 | for(int i=0 ; i<p1.size() ; i++) p.pb(p1[i]) ;
| ~^~~~~~~~~~
squad.cpp:189:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<PT>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
189 | for(int i=0 ; i<p2.size() ; i++) p.pb(p2[i]) ;
| ~^~~~~~~~~~
squad.cpp: In function 'void Init(std::vector<int>, std::vector<int>, std::vector<int>)':
squad.cpp:217:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<PT>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
217 | for(int i=0 ; i<hull.size() ; i++)
| ~^~~~~~~~~~~~
/tmp/ccODg68q.o: In function `main':
grader.cpp:(.text.startup+0x1e8): undefined reference to `BestSquad(int, int)'
collect2: error: ld returned 1 exit status
