#include "aliens.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;
using i64 = long long;
using d64 = long double;
using pi = pair<int, int>;
using pli = pair<i64, i64>;
using ti = tuple<int, int, int>;
using tli = tuple<i64, i64, i64>;
#define iterall(cont) cont.begin(), cont.end()
#define prec(n) setprecision(n) << fixed
const i64 inf = numeric_limits<i64>::max() / 3;
class Line {
public:
i64 a, b;
Line() { a = 0, b = inf; }
Line(i64 _a, i64 _b) { a = _a, b = _b; }
inline i64 get(i64 x) { return a * x + b; }
};
class Node {
public:
i64 s, e;
Line v;
Node *l, *r;
Node() {
s = e = 0;
v = Line();
l = r = nullptr;
}
Node(i64 _s, i64 _e) {
s = _s, e = _e;
v = Line();
l = r = nullptr;
}
Node(i64 _s, i64 _e, i64 _a, i64 _b) {
s = _s, e = _e;
v = Line(_a, _b);
l = r = nullptr;
}
};
namespace LiChao {
Node* init(i64 s, i64 e) { return new Node(s, e); }
void update(Node* here, const Line d) {
i64 s = here->s, e = here->e;
i64 m = (s + e) / 2;
auto lo = here->v, hi = d;
if (lo.get(s) > hi.get(s)) swap(lo, hi);
if (lo.get(e) < hi.get(e)) {
here->v = lo;
return;
}
if (lo.get(m) < hi.get(m)) {
here->v = lo;
if (!here->r) here->r = new Node(m + 1, e);
update(here->r, hi);
} else {
here->v = hi;
if (!here->l) here->l = new Node(s, m);
update(here->l, lo);
}
}
i64 query(Node* here, const i64 x) {
if (!here) return inf;
i64 s = here->s, e = here->e;
i64 m = (s + e) / 2;
return min(here->v.get(x), x <= m ? query(here->l, x) : query(here->r, x));
}
}; // namespace LiChao
inline i64 sq(const i64& x) {
return x * x;
}
inline i64 sq(i64&& x) {
return x * x;
}
i64 take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
vector<pi> cords(n);
for (int i = 0; i < n; i++) cords[i] = {min(r[i], c[i]), max(r[i], c[i])};
sort(iterall(cords), [](pi l, pi r) {
return l.first == r.first ? l.second > r.second : l.first < r.first;
});
cords.erase(unique(iterall(cords)), cords.end());
vector<i64> xc(1), yc(1);
for (auto [x, y] : cords) {
if (yc.size() == 1 || yc.back() < y) {
xc.emplace_back(x);
yc.emplace_back(y);
}
}
for (auto& y : yc) ++y;
const int N = xc.size() - 1;
// for (int i = 1; i <= N; i++) cout << xc[i] << " " << yc[i] << endl;
vector<Node*> roots(k + 1);
for (int i = 0; i <= k; i++) roots[i] = LiChao::init(-1000001, 1000001);
roots[0]->v.b = 0;
vector<vector<i64>> D(N + 1, vector<i64>(k + 1, inf));
for (int i = 1; i <= N; i++) {
for (int j = k; j >= 1; j--) {
if (j == 1) {
D[i][j] = sq(yc[i] - xc[1]);
} else {
D[i][j] = sq(yc[i]) + LiChao::query(roots[j - 1], yc[i]);
}
// cout << i << " " << j << " " << D[i][j] << endl;
if (i != N && D[i][j] < inf) {
LiChao::update(roots[j],
Line(-2 * xc[i + 1],
D[i][j] - sq(max(0LL, yc[i] - xc[i + 1])) + sq(xc[i + 1])));
}
}
}
i64 ret = inf;
for (int j = 1; j <= k; j++) ret = min(ret, D[N][j]);
return ret;
}
