#include using namespace std; int distanceSquared (int x1, int y1, int x2, int y2) { return (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2); } class Island { public: Island (int width, int height) : wide(width), high(height), zero(0) {taxes = new int[high*wide];} ~Island() {delete [] taxes;} int& operator() (int x, int y); int getWidth() {return wide;} int getHeight() {return high;} int taxCollection (int myX, int myY, int hisX, int hisY); private: int wide; int high; int* taxes; int zero; }; int& Island::operator() (int x, int y) { if (x >= 0 && x < wide && y >= 0 && y < high) return taxes[x + wide*y]; else return zero; } int Island::taxCollection (int myX, int myY, int hisX, int hisY) { int sum = 0; for (int x = myX-6; x <= myX+6; ++x) for (int y = myY-6; y <= myY+6; ++y) if (distanceSquared(x, y, myX, myY) <= 36) if (distanceSquared(x, y, myX, myY) < distanceSquared(x, y, hisX, hisY)) sum += operator()(x,y); return sum; } istream& operator>> (istream& in, Island& island) { for (int y = 0; y < island.getHeight(); ++y) for (int x = 0; x < island.getWidth(); ++x) { int d; in >> d; island(x,y) = d; } return in; } int selectHisPosition (Island& island, int myX, int myY, int& hisX, int& hisY) { int bestTaxAmount = -10000; for (int y = 0; y < island.getHeight(); ++y) for (int x = 0; x < island.getWidth(); ++x) { if (island(x,y) > 0.0 && distanceSquared(x, y, myX, myY) > 9) { int hisTaxes = island.taxCollection (x, y, myX, myY); int myTaxes = island.taxCollection (myX, myY, x, y); #ifndef ERROR1 int d = hisTaxes - myTaxes; #else int d = hisTaxes; #endif if (d > bestTaxAmount) { bestTaxAmount = d; hisX = x; hisY = y; } } } return bestTaxAmount; } int selectMyPosition (Island& island, int& myX, int& myY, int hisX, int& hisY) { int bestProfit = -10000; for (int y = 0; y < island.getHeight(); ++y) for (int x = 0; x < island.getWidth(); ++x) { if (island(x,y) > 0.0) { selectHisPosition (island, x, y, hisX, hisY); int hisTaxes = island.taxCollection (hisX, hisY, x, y); int myTaxes = island.taxCollection (x, y, hisX, hisY); #ifndef ERROR2 int d = myTaxes - hisTaxes; #else int d = myTaxes; #endif if (d > bestProfit) { bestProfit = d; myX = x; myY = y; } } } return bestProfit; } void listAllSolutions (Island& island, int profit) { int hisX, hisY; for (int y = 0; y < island.getHeight(); ++y) for (int x = 0; x < island.getWidth(); ++x) { if (island(x,y) > 0.0) { selectHisPosition (island, x, y, hisX, hisY); int hisTaxes = island.taxCollection (hisX, hisY, x, y); int myTaxes = island.taxCollection (x, y, hisX, hisY); int d = myTaxes - hisTaxes; if (d == profit) { cout << "Possible solution: " << x << " " << y << endl; } } } } int main () { int w, h; cin >> w >> h; Island island (w, h); cin >> island; int myX, myY, hisX, hisY; int profit; profit = selectMyPosition (island, myX, myY, hisX, hisY); profit = selectHisPosition (island, myX, myY, hisX, hisY); cout << "Place your castle at: " << myX << " " << myY << endl; cout << "My choice: " << myX << ' ' << myY << endl; cout << "His choice: " << hisX << ' ' << hisY << endl; cout << "My Taxes: " << island.taxCollection (myX, myY, hisX, hisY) << endl; cout << "His Taxes: " << island.taxCollection (hisX, hisY, myX, myY) << endl; listAllSolutions (island, island.taxCollection (myX, myY, hisX, hisY) - island.taxCollection (hisX, hisY, myX, myY)); return 0; }