This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#include<chrono>
using namespace std;
using namespace chrono;
#define all(a) a.begin(), a.end()
#define sz(x) (int(x.size()))
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef vector<string> vs;
template<class T1, class T2>
istream &operator>>(istream &in, pair<T1, T2> &P){
in >> P.first >> P.second;
return in;
}
template<class T1, class T2>
ostream &operator<<(ostream &out, const pair<T1, T2> &P){
out << "(" << P.first << ", " << P.second << ")";
return out;
}
template<class T>
istream &operator>>(istream &in, vector<T> &arr){
for(auto &x: arr) in >> x;
return in;
}
template<class T>
ostream &operator<<(ostream &out, const vector<T> &arr){
for(auto &x: arr) out << x << ' '; cout << "\n";
return out;
}
template<class T>
istream &operator>>(istream &in, deque<T> &arr){
for(auto &x: arr) in >> x;
return in;
}
template<class T>
ostream &operator<<(ostream &out, const deque<T> &arr){
for(auto &x: arr) out << x << ' '; cout << "\n";
return out;
}
struct point{
ll x, y;
int ind;
point(pll p): x(p.first), y(p.second){}
point(ll x = 0, ll y = 0, int ind = 0): x(x), y(y), ind(ind){}
bool operator<(const point &other) const{
return x < other.x || (x == other.x && y < other.y);
}
point operator+(const point &other) const{
return point(x + other.x, y + other.y);
}
point operator+=(const point &other){
return *this = *this + other;
}
point operator-(const point &other) const{
return point(x - other.x, y - other.y);
}
point operator-=(const point &other){
return *this = *this - other;
}
ll operator*(const point &other) const{
return x * other.x + y * other.y;
}
};
ostream &operator<<(ostream &out, point p){
cout << "(" << p.x << ", " << p.y << ", " << p.ind << ")";
return out;
}
ll ori(const point &p, const point &q, const point &r){
return p.x * q.y + q.x * r.y + r.x * p.y - p.y * q.x - q.y * r.x - r.y * p.x;
}
struct convhull{
int N, L, U;
vector<point> ch;
convhull(vector<point> arr = vector<point>()){
if(arr.size() <= 1){
ch = arr;
N = L = U = arr.size();
return;
}
sort(arr.begin(), arr.end());
vector<point> upper, lower;
point p = arr.front(), q = arr.back();
upper.push_back(p), lower.push_back(p);
for(int i = 1; i < arr.size(); i ++){
if(i == arr.size() - 1 || ori(p, arr[i], q) < 0){
while(upper.size() >= 2 && ori(upper[upper.size() - 2], upper[upper.size() - 1], arr[i]) >= 0){
upper.pop_back();
}
upper.push_back(arr[i]);
}
if(i == arr.size() - 1 || ori(p, arr[i], q) > 0){
while(lower.size() >= 2 && ori(lower[lower.size() - 2], lower[lower.size() - 1], arr[i]) <= 0){
lower.pop_back();
}
lower.push_back(arr[i]);
}
}
U = upper.size(), L = lower.size();
for(int i = 0; i < L; i ++) ch.push_back(lower[i]);
for(int i = U - 2; i; i --) ch.push_back(upper[i]);
N = ch.size();
}
int max_element(ll x, ll y){
point p(x, y);
int l = L - 1, r = N;
while(r - l > 3){
int m1 = (2 * l + r) / 3, m2 = (l + 2 * r) / 3;
p * ch[m1] <= p * ch[m2] ? l = m1 : r = m2;
}
int res = l;
for(int i = l + 1; i < r; i ++) if(p * ch[res] < p * ch[i]) res = i;
return res;
}
int min_element(ll x, ll y){
point p(x, y);
int l = 0, r = L;
while(r - l > 3){
int m1 = (2 * l + r) / 3, m2 = (l + 2 * r) / 3;
p * ch[m1] >= p * ch[m2] ? l = m1 : r = m2;
}
int res = l;
for(int i = l + 1; i < r; i ++) if(p * ch[res] > p * ch[i]) res = i;
return res;
}
};
int n;
vector<vector<convhull>> c(2, vector<convhull>(2));
void Init(vi a, vi d, vi p){
n = a.size();
vector<vector<point>> data(2, vector<point>(n));
for(int i = 0; i < n; i ++) data[0][i] = point(a[i], p[i], i), data[1][i] = point(d[i], p[i], i);
for(int i = 0; i < 2; i ++){
c[i][0] = convhull(data[i]);
vi used(n);
for(auto &p: c[i][0].ch) used[p.ind] = true;
vector<point> temp;
for(int j = 0; j < n; j ++) if(!used[j]) temp.push_back(data[i][j]);
c[i][1] = convhull(temp);
}
}
ll BestSquad(int x, int y){
vector<vector<point>> p(2, vector<point>(2));
point t(x, y);
for(int i = 0; i < 2; i ++){
int u = c[i][0].max_element(x, y), pu = (u + c[i][0].N - 1) % c[i][0].N, nu = (u + 1) % c[i][0].N;
p[i][0] = c[i][0].ch[u];
p[i][1] = t * c[i][0].ch[pu] <= t * c[i][0].ch[nu] ? c[i][0].ch[nu] : c[i][0].ch[pu];
if(c[i][1].N){
auto temp = c[i][1].ch[c[i][1].max_element(x, y)];
if(t * p[i][1] < t * temp) p[i][1] = temp;
}
}
if(p[0][0].ind == p[1][0].ind){
return max((p[0][0] + p[1][1]) * t, (p[0][1] + p[1][0]) * t);
}
else{
return (p[0][0] + p[1][0]) * t;
}
}
/*
6
2 1 1
2 1 2
2 1 3
2 1 4
2 1 5
2 1 6
100
4
3 1 4
2 3 3
2 1 6
4 4 1
2
1 3
3 1
*/
//////////////////////////////////////////////////////////////////////////////////////////////////////
// //
// //
// _____________ //
// ++++++++++ ___------------------\\\\ //
// +++`+``+`+`++++ ///`````````````````````````````\\\ //
// ++`+`+``+++`++++ /////```````````````````````````````````\\ //
// +++`++`+`+``+++/////`````````````````````````````````````````\\ //
// +++`++`+``+///```````````|```````````````````````````````````\\ //
// ____++++/++++/`````````````/````````|````````|```````````````````\\ //
// / / / | //``````````````|````````|```````|````````|````````````\\ //
// / / / | ///````````/```````|```````||```````|````````|``````\```````\\ //
// | / / |///`````````|``````/````````|````````|````````|```````|```````\\ //
// |/ | |//``|```````|``````|````````|`````````|```````|```````|````````\\ //
// /\___|__//`|``|```````|` | ``:|````````|:```````|```````|```|`````| //
// / / /``|``|``````|/ | :| ```:|```````|```````|``++````++ //
// / / //```|``|``````| | |: :| ```|```````|```++``++`\ //
// | / /````|``|``````/ _.::::. | | | ````|```|`++`\`| //
// | / |````|``|`````| ` | ``|```++``++`| //
// | / |````|``|`````| : |``++````++| //
// | / /````|``|`````| _.-:::. |..`|``.`|.| //
// |/ /`````|``|`````| ` |```|````|`| //
// /| |`````|``|`````| :' .|```|````|.| //
// / | |`````|``|`````| /|-|``|````|`| //
// / | |`````|```\````| / ||```|````|``\ //
// / | |`````|````|```|:: /_| ||```|````|``| //
// |`````|````|```|:|:. `.._ .\___/:|```|````|``| //
// |`````\````|```|:|::- ``:::.... -:|:|:::|```|````|``| //
// |``````|```|```|:|::`|. .:::|:|:::|```|````|``| //
// \`````|```|```|:|::/|--. .`:|:::|:|:::/```|````|``| //
// |````|```|```\:|:|:|----- _..-:|:|:|:::|:|::|````|````|`/ //
// |````|```|````\|:|:|-------.____.....------|/::|:::|:|::|````|````|`| //
// |````|```|\````\:|/\___________ ________/\--\:::|:|::|````/````|`| //
// |````\```| \```|:/-------------\ /----------\``\::|:|::|```/`````|`| //
// |`````|``| \``|/---------------\/------------\_________|```|`````|`| //
// //
//////////////////////////////////////////////////////////////////////////////////////////////////////
// //
// Created by Aeren //
// //
//////////////////////////////////////////////////////////////////////////////////////////////////////
Compilation message (stderr)
squad.cpp: In function 'std::ostream& operator<<(std::ostream&, const std::vector<_Tp>&)':
squad.cpp:32:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
for(auto &x: arr) out << x << ' '; cout << "\n";
^~~
squad.cpp:32:37: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
for(auto &x: arr) out << x << ' '; cout << "\n";
^~~~
squad.cpp: In function 'std::ostream& operator<<(std::ostream&, const std::deque<_Tp>&)':
squad.cpp:42:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
for(auto &x: arr) out << x << ' '; cout << "\n";
^~~
squad.cpp:42:37: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
for(auto &x: arr) out << x << ' '; cout << "\n";
^~~~
squad.cpp: In constructor 'convhull::convhull(std::vector<point>)':
squad.cpp:90:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 1; i < arr.size(); i ++){
~~^~~~~~~~~~~~
squad.cpp:91:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(i == arr.size() - 1 || ori(p, arr[i], q) < 0){
~~^~~~~~~~~~~~~~~~~
squad.cpp:97:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(i == arr.size() - 1 || ori(p, arr[i], q) > 0){
~~^~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |