#include #include #include #include #include #include #include #include using namespace std; #ifdef _MSC_VER typedef unsigned __int64 uint64_t; typedef unsigned __int32 uint32_t; #endif typedef uint32_t ui; struct rug { int x1, y1, x2, y2; rug(int x1_, int y1_, int x2_, int y2_) : x1(x1_),y1(y1_),x2(x2_),y2(y2_) {} ui area() { return (x2-x1+1)*(y2-y1+1); } string tostr() const { char buf[128]; sprintf(buf, "%d %d %d %d", x1, y1, x2, y2); return string(buf); } }; ui overlap(const rug &r1, const rug &r2) { int x1 = max(r1.x1, r2.x1); int y1 = max(r1.y1, r2.y1); int x2 = min(r1.x2, r2.x2); int y2 = min(r1.y2, r2.y2); if(x1>x2 || y1>y2) return 0; else return (x2-x1+1)*(y2-y1+1); } inline bool between(int a, int b, int x) { return (x>=a && x <= b); } void process(string s) { ui w, h; { istringstream ss(s); ss >> w >> h; } ui area_rug = 0; list rugs; while(1) { char buf[1024]; cin.getline(buf, 1024); s = buf; istringstream ss(s); rug r(0,0,0,0); ss >> r.x2 >> r.y2 >> r.x1 >> r.y1; if(!r.x1 && !r.x2 && !r.y1 && !r.y2) break; r.x2 += r.x1-1; r.y2 += r.y1-1; fprintf(stderr, "%s: area=%lu\n", s.c_str(), r.area()); // Subdivision pass list chunks; chunks.push_back(r); nextchunk: while(!chunks.empty()) { rug c = chunks.front(); chunks.pop_front(); for(list::iterator rug_it = rugs.begin(); rug_it != rugs.end(); rug_it++) { ui ovarea = overlap(c, *rug_it); if(!ovarea) continue; if(ovarea == c.area()) goto nextchunk; fprintf(stderr, "Overlap: (%s) with (%s) --> %lu\n", c.tostr().c_str(), rug_it->tostr().c_str(), ovarea); int x1=c.x1, x2=c.x2, y1=c.y1, y2=c.y2; int rx1=rug_it->x1, rx2=rug_it->x2, ry1=rug_it->y1, ry2=rug_it->y2; if(between(x1+1, x2, rx1)) { chunks.push_back(rug(x1,y1,rx1-1,y2)); chunks.push_back(rug(rx1,y1,x2,y2)); } else if(between(x1, x2-1, rx2)) { chunks.push_back(rug(x1,y1,rx2,y2)); chunks.push_back(rug(rx2+1,y1,x2,y2)); } else if(between(y1+1, y2, ry1)) { chunks.push_back(rug(x1,y1,x2,ry1-1)); chunks.push_back(rug(x1,ry1,x2,y2)); } else if(between(y1, y2-1, ry2)) { chunks.push_back(rug(x1,y1,x2,ry2)); chunks.push_back(rug(x1,ry2+1,x2,y2)); } else fprintf(stderr, "ugh\n"); list::reverse_iterator it = chunks.rbegin(); fprintf(stderr, "Added (%s) and ", it->tostr().c_str()); ++it; fprintf(stderr, "(%s)\n", it->tostr().c_str()); goto nextchunk; } fprintf(stderr, "Chunk (%s) --> area %lu\n", c.tostr().c_str(), c.area()); area_rug += c.area(); } rugs.push_back(r); } printf("Floor has %lu area not covered\n", w*h - area_rug); } int main() { while(cin) { string s; char buf[1024]; cin.getline(buf, 1024); s = string(buf); if(s.empty()) continue; process(s); } return 0; }