#include "aliens.h"
#include <algorithm>
#include <vector>
#include <stdio.h>
typedef struct point point;
struct point
{
long long r, c;
};
point P[100005];
long long DP[2][100005];
int sortP(point a, point b)
{
return (a.r < b.r || (a.r == b.r && a.c < b.c));
}
long long min(long long a, long long b)
{
return (a < b)?a:b;
}
long long max(long long a, long long b)
{
return (a > b)?a:b;
}
typedef struct line line;
struct line
{
long long m, c;
double s;
};
std::vector<line> L;
double intersect(line a, line b)
{
if (a.m == b.m)
{
if (b.c >= a.c)
return 1e18;
else
return -1e18;
}
else
return (double) (a.c - b.c)/(b.m - a.m);
}
void insertLine(line l)
{
// printf("insertLine %lld %lld %lf\n", l.m, l.c, l.s);
double r;
while (!L.empty() && (r = intersect(L.back(), l)) <= L.back().s)
L.pop_back();
if (r == 1e18)
return;
if (L.empty())
{
l.s = -1e18;
L.push_back(l);
}
else
{
l.s = r;
L.push_back(l);
}
}
int compare(line e, long long v)
{
return e.s < v;
}
long long getLine(long long x)
{
// int i;
// for (i = 0; i < L.size(); i++)
// printf("line %lld %lld %lf\n", L[i].m, L[i].c, L[i].s);
int j = std::lower_bound(L.begin(), L.end(), x, compare) - L.begin();
if (j == L.size() || L[j].s > x) j--;
// printf("getLine x%lld j%d %lld\n", x, j, L[j].m*x + L[j].c);
return L[j].m*x + L[j].c;
}
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
int i, j;
long long Ans;
for (i = 0; i < n; i++)
{
P[i].r = min(r[i], c[i]);
P[i].c = max(r[i], c[i]);
}
std::sort(&P[0], &P[n], sortP);
for (j = 0; j < n; j++)
{
DP[1][j] = (P[j].c - P[0].r + 1)*(P[j].c - P[0].r + 1);
// printf("%lld\n", DP[1][j]);
}
// printf("\n");
Ans = DP[1][n - 1];
line l;
double rr;
for (i = 2; i <= k; i++)
{
L.clear();
L.push_back({0, 1000000000000000000LL, -1e18});
for (j = 0; j < n; j++)
{
// if (j > 0)
// insertLine({-2LL*(P[j].r - 1), DP[(i+1)%2][j - 1] + (P[j].r - 1)*(P[j].r - 1), -1e18});
if (j > 0)
{
if (P[j - 1].c >= P[j].r)
insertLine({-2LL*(P[j].r - 1), DP[(i+1)%2][j - 1] - P[j - 1].c*P[j - 1].c + 2LL*P[j - 1].c*(P[j].r - 1), -1e18});
else
insertLine({-2LL*(P[j].r - 1), DP[(i+1)%2][j - 1] + (P[j].r - 1)*(P[j].r - 1), P[j].r + 1, -1e18});
// l = {-2LL*(P[j].r - 1), DP[(i+1)%2][j - 1] + (P[j].r - 1)*(P[j].r - 1), P[j].r + 1};
// if (L.back().s >= l.s)
// L.pop_back();
// while (!L.empty() && (rr = intersect(L.back(), l)) <= L.back().s)
// L.pop_back();
// if (rr != 1e18)
// l.s = rr;
// L.push_back(l);
}
DP[i%2][j] = getLine(P[j].c) + P[j].c*P[j].c;
// printf("%lld\n", DP[i%2][j]);
}
// printf("\n");
Ans = min(Ans, DP[i%2][n - 1]);
}
return Ans;
}
Compilation message
aliens.cpp: In function 'long long int getLine(long long int)':
aliens.cpp:72:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (j == L.size() || L[j].s > x) j--;
~~^~~~~~~~~~~
aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:107:118: error: could not convert '{(-2 * (P[j].point::r - 1)), (DP[((i + 1) % 2)][(j - 1)] + ((P[j].point::r - 1) * (P[j].point::r - 1))), (P[j].point::r + 1), -1.0e+18}' from '<brace-enclosed initializer list>' to 'line'
insertLine({-2LL*(P[j].r - 1), DP[(i+1)%2][j - 1] + (P[j].r - 1)*(P[j].r - 1), P[j].r + 1, -1e18});
^
aliens.cpp:92:10: warning: unused variable 'l' [-Wunused-variable]
line l;
^
aliens.cpp:93:12: warning: unused variable 'rr' [-Wunused-variable]
double rr;
^~
