#include<bits/stdc++.h>
#include<chrono>
using namespace std;
using namespace chrono;
#define all(a) a.begin(), a.end()
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;
point(pll p): x(p.first), y(p.second){}
point(ll x = 0, ll y = 0): x(x), y(y){}
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;
}
};
istream &operator>>(istream &in, point &p){
cin >> p.x >> p.y;
return in;
}
ostream &operator<<(ostream &out, const point &p){
cout << "(" << p.x << ", " << p.y << ")";
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, R;
vector<point> ch;
convhull(vector<point> arr = vector<point>(), bool sorted = false){
if(arr.size() <= 1){
ch = arr;
N = R = arr.size();
if(N) R --;
return;
}
if(!sorted) 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]);
}
}
for(int i = 0; i < lower.size(); i ++) ch.push_back(lower[i]);
for(int i = upper.size() - 2; i; i --) ch.push_back(upper[i]);
N = ch.size(), R = lower.size() - 1;
}
vector<point> linearize() const{
if(N <= 1) return ch;
int i = 0, j = N - 1;
vector<point> res(N);
int cnt = 0;
while(i != R && j != R){
if(ch[i] < ch[j]) res[cnt ++] = ch[i ++];
else res[cnt ++] = ch[j --];
}
while(i < R) res[cnt ++] = ch[i ++];
while(j > R) res[cnt ++] = ch[j --];
res.back() = ch[R];
return res;
}
int max_element(ll x, ll y){
point p(x, y);
int l = R, 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;
}
convhull operator+(const convhull &other) const{
if(!N || !other.N) return convhull();
vector<point> temp1(ch), temp2(other.ch);
for(int i = 0; i + 1 < N; i ++) temp1[i] = ch[i + 1] - ch[i];
for(int i = 0; i + 1 < other.N; i ++) temp2[i] = other.ch[i + 1] - other.ch[i];
temp1.back() = ch.front() - ch.back();
temp2.back() = other.ch.front() - other.ch.back();
function<bool(point, point)> cmp = [&](point p, point q){
int typep = 1, typeq = 1;
if(p.x > 0 || !p.x && p.y >= 0) typep = 0;
if(q.x > 0 || !q.x && q.y >= 0) typeq = 0;
if(typep != typeq) return typep < typeq;
return ori(p, q, point(0, 0)) > 0;
};
vector<point> temp(N + other.N);
int cnt = 0;
int i = 0, j = 0;
while(i < N && j < other.N){
if(cmp(temp1[i], temp2[j])) temp[cnt ++] = temp1[i ++];
else temp[cnt ++] = temp2[j ++];
}
for(; i < N; i ++) temp[cnt ++] = temp1[i ++];
for(; j < other.N; j ++) temp[cnt ++] = temp2[j ++];
convhull res;
res.N = N + other.N;
res.ch.resize(res.N);
cnt = 0;
res.ch[cnt ++] = ch[0] + other.ch[0];
for(int i = 0; i + 1 < res.N; i ++){
res.ch[cnt ++] = res.ch[cnt - 1] + temp[i];
}
res.R = std::max_element(all(res.ch)) - res.ch.begin();
return res;
}
convhull operator^(const convhull &other) const{
if(!N) return other;
if(!other.N) return *this;
auto temp1 = linearize(), temp2 = other.linearize();
vector<point> res(temp1.size() + temp2.size());
merge(all(temp1), all(temp2), res.begin());
return convhull(res, true);
}
convhull operator-() const{
convhull res(*this);
res.R = N - R;
if(N == 1) res.R = 0;
for(int i = 0; i + R < N; i ++) res.ch[i] = point(-ch[i + R].x, -ch[i + R].y);
for(int i = N - R; i < N; i ++) res.ch[i] = point(-ch[i + R - N].x, -ch[i + R - N].y);
return res;
}
};
convhull c;
typedef tuple<convhull, convhull, convhull> tccc;
void Init(vi a, vi d, vi p){
int 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]), data[1][i] = point(d[i], p[i]);
function<tccc(int, int)> solve = [&](int l, int r){
if(r - l == 1){
return tccc(convhull({data[0][l]}), convhull({data[1][l]}), convhull());
}
int m = l + r >> 1;
auto [p1, p2, p3] = solve(l, m);
auto [q1, q2, q3] = solve(m, r);
return tccc(p1 ^ q1, p2 ^ q2, p1 + q2 ^ p2 + q1 ^ (p3 ^ q3));
};
c = get<2>(solve(0, n));
}
ll BestSquad(int x, int y){
int p = c.max_element(x, y);
return point(x, y) * c.ch[p];
}
/*
12
6 1 1
5 1 2
4 1 3
3 1 4
2 1 5
1 1 6
6 1 1
5 1 2
4 1 3
3 1 4
2 1 5
1 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
squad.cpp: In function 'std::ostream& operator<<(std::ostream&, const std::vector<_Tp>&)':
squad.cpp:31:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
for(auto &x: arr) out << x << ' '; cout << "\n";
^~~
squad.cpp:31: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:41:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
for(auto &x: arr) out << x << ' '; cout << "\n";
^~~
squad.cpp:41: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>, bool)':
squad.cpp:93:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 1; i < arr.size(); i ++){
~~^~~~~~~~~~~~
squad.cpp:94:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(i == arr.size() - 1 || ori(p, arr[i], q) < 0){
~~^~~~~~~~~~~~~~~~~
squad.cpp:100:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(i == arr.size() - 1 || ori(p, arr[i], q) > 0){
~~^~~~~~~~~~~~~~~~~
squad.cpp:107:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < lower.size(); i ++) ch.push_back(lower[i]);
~~^~~~~~~~~~~~~~
squad.cpp: In lambda function:
squad.cpp:145:23: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
if(p.x > 0 || !p.x && p.y >= 0) typep = 0;
~~~~~^~~~~~~~~~~
squad.cpp:146:23: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
if(q.x > 0 || !q.x && q.y >= 0) typeq = 0;
~~~~~^~~~~~~~~~~
squad.cpp: In member function 'convhull convhull::operator+(const convhull&) const':
squad.cpp:165:15: warning: operation on 'cnt' may be undefined [-Wsequence-point]
res.ch[cnt ++] = res.ch[cnt - 1] + temp[i];
~~~~^~
squad.cpp: In lambda function:
squad.cpp:197:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m = l + r >> 1;
~~^~~
squad.cpp:200:36: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
return tccc(p1 ^ q1, p2 ^ q2, p1 + q2 ^ p2 + q1 ^ (p3 ^ q3));
~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Correct |
8 ms |
380 KB |
Output is correct |
| 3 |
Correct |
1870 ms |
21496 KB |
Output is correct |
| 4 |
Correct |
1870 ms |
21496 KB |
Output is correct |
| 5 |
Correct |
170 ms |
7272 KB |
Output is correct |
| 6 |
Correct |
2954 ms |
107648 KB |
Output is correct |
| 7 |
Correct |
2981 ms |
111020 KB |
Output is correct |
| 8 |
Correct |
2928 ms |
106936 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Correct |
16 ms |
504 KB |
Output is correct |
| 3 |
Correct |
1732 ms |
21464 KB |
Output is correct |
| 4 |
Correct |
1739 ms |
21496 KB |
Output is correct |
| 5 |
Correct |
101 ms |
3512 KB |
Output is correct |
| 6 |
Correct |
2841 ms |
78096 KB |
Output is correct |
| 7 |
Correct |
2860 ms |
80076 KB |
Output is correct |
| 8 |
Correct |
2848 ms |
77892 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Correct |
8 ms |
380 KB |
Output is correct |
| 3 |
Correct |
1870 ms |
21496 KB |
Output is correct |
| 4 |
Correct |
1870 ms |
21496 KB |
Output is correct |
| 5 |
Correct |
170 ms |
7272 KB |
Output is correct |
| 6 |
Correct |
2954 ms |
107648 KB |
Output is correct |
| 7 |
Correct |
2981 ms |
111020 KB |
Output is correct |
| 8 |
Correct |
2928 ms |
106936 KB |
Output is correct |
| 9 |
Correct |
2 ms |
256 KB |
Output is correct |
| 10 |
Correct |
16 ms |
504 KB |
Output is correct |
| 11 |
Correct |
1732 ms |
21464 KB |
Output is correct |
| 12 |
Correct |
1739 ms |
21496 KB |
Output is correct |
| 13 |
Correct |
101 ms |
3512 KB |
Output is correct |
| 14 |
Correct |
2841 ms |
78096 KB |
Output is correct |
| 15 |
Correct |
2860 ms |
80076 KB |
Output is correct |
| 16 |
Correct |
2848 ms |
77892 KB |
Output is correct |
| 17 |
Correct |
75 ms |
3712 KB |
Output is correct |
| 18 |
Correct |
23 ms |
764 KB |
Output is correct |
| 19 |
Correct |
2033 ms |
22136 KB |
Output is correct |
| 20 |
Correct |
2035 ms |
22080 KB |
Output is correct |
| 21 |
Incorrect |
122 ms |
5424 KB |
Output isn't correct |
| 22 |
Halted |
0 ms |
0 KB |
- |
