#include #include #include #include #include #include #include using namespace std; //A result returned from a search. typedef struct _SearchResult { int value; bool found; } SearchResult; // Returns the element of vec that is closest to and ABOVE value SearchResult upperNeighbor(int value, vector& vec) { SearchResult result; result.found = false; if (vec.size() == 0) return result; if (value >= vec[vec.size()-1]) return result; vector::iterator iter = upper_bound(vec.begin(), vec.end(), value); result.value = *iter; result.found = true; return result; } // Returns the element of vec that is closest to and BELOW value SearchResult lowerNeighbor(int value, vector& vec) { SearchResult result; result.found = false; if (vec.size() == 0) return result; if (value <= vec[0]) return result; vector::iterator iter = lower_bound(vec.begin(), vec.end(), value); iter--; result.value = *iter; result.found = true; return result; } int main() { ifstream infile("park.in"); ofstream outfile("park.out"); while (true) { int numTrees, numPaths; infile >> numTrees >> numPaths; if (numTrees == 0 && numPaths == 0) return 0; //Basic list of trees, storing the x and y coordinates vector > trees; //List of trees in 2 forms: Mapping x coordinates to list of y's, and y's to list of x's map > ytox, xtoy; //List of horizontal and vertical paths vector horizPaths, vertPaths; //Input the trees for (int i =0; i < numTrees; i++) { int x, y; infile >> x >> y; xtoy[x].push_back(y); ytox[y].push_back(x); trees.push_back(make_pair(x, y)); } //Input the paths for (int i = 0; i < numPaths; i++) { string str; infile >> str; int value = atoi(str.substr(2).c_str()); if (str[0] == 'x') vertPaths.push_back(value); else horizPaths.push_back(value); } //Sort the lists of paths sort(vertPaths.begin(), vertPaths.end()); sort(horizPaths.begin(), horizPaths.end()); //Sort each list of coordinates in the X-to-Y and Y-to-X maps map >::iterator iter; for (iter = xtoy.begin(); iter != xtoy.end(); iter++) { vector& vec = iter->second; sort(vec.begin(), vec.end()); } for (iter = ytox.begin(); iter != ytox.end(); iter++) { vector& vec = iter->second; sort(vec.begin(), vec.end()); } int numVisible = 0; //Iterate through the trees and see if they can be visible from any side for (int i = 0; i < trees.size(); i++) { SearchResult nextTree, nextPath; int thisX = trees[i].first; int thisY = trees[i].second; bool visible = false; //Visible from above? nextTree = upperNeighbor(thisY, xtoy[thisX]); nextPath = upperNeighbor(thisY, horizPaths); //Path must exist, and nearest tree either doesn't exists or is above the path. if (nextPath.found && (!nextTree.found || nextTree.value > nextPath.value)) visible = true; //Visible from below? nextTree = lowerNeighbor(thisY, xtoy[thisX]); nextPath = lowerNeighbor(thisY, horizPaths); //Path must exist, and nearest tree either doesn't exists or is below the path. if (nextPath.found && (!nextTree.found || nextTree.value < nextPath.value)) visible = true; //Visible from the right? nextTree = upperNeighbor(thisX, ytox[thisY]); nextPath = upperNeighbor(thisX, vertPaths); //Path must exist, and nearest tree either doesn't exists or is right of the path. if (nextPath.found && (!nextTree.found || nextTree.value > nextPath.value)) visible = true; //Visible from the left? nextTree = lowerNeighbor(thisX, ytox[thisY]); nextPath = lowerNeighbor(thisX, vertPaths); //Path must exist, and nearest tree either doesn't exists or is left of the path. if (nextPath.found && (!nextTree.found || nextTree.value < nextPath.value)) visible = true; if (visible) numVisible++; } outfile << numVisible << endl; } return 0; }