zoj 2605 Under Control

zoj 2605 Under Control

#include<iostream>#include<sstream>#include<vector>#include<list>#include<deque>#include<queue>#include<stack>#include<map>#include<set>#include<bitset>#include<algorithm>#include<cstdio>#include<cstdlib>#include<cstring>#include<cctype>#include<cmath>#include<ctime>using namespace std;const double eps(1e-8);typedef long long lint;#define clr(x) memset( x , 0 , sizeof(x) )#define sz(v) ((int)(v).size())#define rep(i, n) for (int i = 0; i < (n); ++i)#define repf(i, a, b) for (int i = (a); i <= (b); ++i)#define repd(i, a, b) for (int i = (a); i >= (b); --i)#define clrs( x , y ) memset( x , y , sizeof(x) )struct point { int x, y; point (int _x = 0, int _y = 0) : x(_x), y(_y) { } bool operator < (const point &p) const { if (x != p.x) return x < p.x; else return y < p.y; } bool operator == (const point &p) const { return x == p.x && y == p.y; }};int bx[] = {-1, 0, 1, 0, -1, 1, 1, -1};int by[] = {0, 1, 0, -1, 1, 1, -1, -1};int bbx[] = {-1, -1, 0, 1, 1, 1, 0, -1};int bby[] = {0, 1, 1, 1, 0, -1, -1, -1};vector<point> a;map<point, int> mp, v;queue<point> que;bool ok(const point &p) { int nx1, nx2, ny1, ny2, nx3, ny3; for (int i = 0; i <= 6; i += 2) { nx1 = p.x + bbx[i]; ny1 = p.y + bby[i]; nx2 = p.x + bbx[i + 1]; ny2 = p.y + bby[i + 1]; nx3 = p.x + bbx[(i + 2) % 8]; ny3 = p.y + bby[(i + 2) % 8];  if (mp.count(point(nx1, ny1)) == 0 &&  mp.count(point(nx2, ny2)) == 0 &&  mp.count(point(nx3, ny3)) == 0) { return false; } } return true;}void gao() { v.clear(); for (map<point, int>::iterator it = mp.begin(); it != mp.end(); it++) { rep (i, 8) { int nx = it->first.x + bx[i]; int ny = it->first.y + by[i]; point p = point(nx, ny); if (v.count(p) == 0 && mp.count(p) == 0) { que.push(p); v[p] = 1; } } }  while (!que.empty()) { point px = que.front(); que.pop(); v[px] = 0; if (ok(px)) { mp[px] = 1; rep (i, 8) { int nx = px.x + bx[i]; int ny = px.y + by[i]; point p = point(nx, ny); if (v[p] == 0 && mp.count(p) == 0) { que.push(p); v[p] = 1; } } } }}int dis(int x1, int y1, int x2, int y2) { return abs(x1 - x2) + abs(y1 - y2);}int main(){ int n; while (scanf("%d", &n) == 1) { if (n == 0) break; mp.clear(); rep (i, n) { int x, y, z; scanf("%d%d%d", &x, &y, &z); z++; repf (i, x - z, x + z) { repf (j, y - z, y + z) { if (dis(i, j, x, y) <= z + 1) { mp[point(i, j)] = 1; } }  } } gao(); printf("%dn", sz(mp));  } return 0;}