Skip to content

Instantly share code, notes, and snippets.

@key-moon

key-moon/c.cpp Secret

Created October 25, 2020 15:44
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save key-moon/cab7c6e64ce1411b1e7ad424bd665d75 to your computer and use it in GitHub Desktop.
Save key-moon/cab7c6e64ce1411b1e7ad424bd665d75 to your computer and use it in GitHub Desktop.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define var auto
const char newl = '\n';
template< typename T1, typename T2 >
inline void chmin(T1 &a, T2 b) { if (a > b) a = b; }
template< typename T1, typename T2 >
inline void chmax(T1 &a, T2 b) { if (a < b) a = b; }
int main(){
int n;
cin >> n;
if (n == 0) return 0;
int sx, sy, gx, gy;
cin >> sx >> sy >> gx >> gy;
int offx = sx, offy = sy;
sx -= offx, sy -= offy, gx -= offx, gy -= offy;
int parx = gx < 0 ? -1 : 1;
int pary = gy < 0 ? -1 : 1;
gx *= parx, gy *= pary;
using P = pair<int, int>;
using PP = pair<P, int>;
vector<PP> ses{};
vector<vector<int>> dadds(gy + 1, vector<int>(gx + 1));
vector<vector<int>> radds(gy + 1, vector<int>(gx + 1));
int init = 0;
var incr = [&](vector<vector<int>>& v, int i, int j){
if (i < 0 || gy < i || j < 0 || gx < j) return;
v[i][j]++;
return;
};
for (int i = 0; i < n; i++){
int x, y, r;
cin >> x >> y >> r;
y = (y - offy) * pary;
x = (x - offx) * parx;
var tx = x - r, ty = y - r;
var bx = x + r, by = y + r;
if (ty <= 0 && 0 <= by && tx <= 0 && 0 <= bx){
init++;
continue;
}
for (int i = tx; i <= bx; i++){
incr(dadds, ty, i);
}
for (int i = ty; i <= by; i++){
incr(radds, i, tx);
}
/*cout << endl;
cout << x << " " << y << " " << r << endl;
cout << tx << " " << ty << bx << " " << by << endl;
for (int i = 0; i <= gy; i++){
for (int j = 0; j <= gx; j++){
cout << (radds[i][j] | dadds[i][j] ? "#" : ".");
}
cout << endl;
}*/
}
vector<vector<int>> dp(gy + 1, vector<int>(gx + 1, INT32_MAX / 2));
{
dp[0][0] = init;
for (int j = 1; j <= gx; j++){
dp[0][j] = dp[0][j - 1] + radds[0][j];
}
}
for (int i = 1; i <= gy; i++){
dp[i][0] = dp[i - 1][0] + dadds[i][0];
for (int j = 1; j <= gx; j++){
dp[i][j] = min(dp[i][j - 1] + radds[i][j], dp[i - 1][j] + dadds[i][j]);
}
}
cout << dp[gy][gx] << endl;
main();
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment