#include <map> #include <set> #include <vector> #include <iostream> #include <algorithm> using namespace std; typedef pair<int,int> point; struct CoverSet { map<point,int> covcnt; set<point> cover1; void cover (const point& p, int mult = 1) { if (covcnt[p] == 1) { cover1.erase (p); } covcnt[p] += mult; if (covcnt[p] == 1) { cover1.insert (p); } } set<point>::const_iterator cover1_begin () const { return cover1.begin(); } set<point>::const_iterator cover1_end () const { return cover1.end(); } size_t size() const { return covcnt.size(); } }; int main (int ac, char **av) { int round = 0; vector<point> newlist; newlist.push_back(point(0,0)); size_t tot = 0; bool dir = false; CoverSet c; for (;;) { ++round; tot += newlist.size(); cout << round << " " << tot << " " << newlist.size() << " " << c.size() << " " << endl; for (vector<point>::iterator i = newlist.begin(); i != newlist.end(); ++i) { c.cover(*i, 2); if (dir) { c.cover (point(i->first, i->second-1)); c.cover (point(i->first, i->second+1)); } else { c.cover (point(i->first-1, i->second)); c.cover (point(i->first+1, i->second)); } } dir = !dir; newlist.clear(); copy (c.cover1_begin(), c.cover1_end(), back_inserter(newlist)); } }