|
|
back to boardWeird Overlapping problem Posted by dimroed 18 Feb 2002 08:09 For ~2 of the testcases (on USACO training for same problem), I get a weird overlap, and my area for one of the colours is a bit bigger than that of the real output. Can anyone tell me where my mistake is? Here's my algorithm, which basically reads in the rectangles and is supposed to go back through existing rectangles and reshape them so that there is no overlap. ---------------------------------------------- #include <fstream.h> #include <stdlib.h> struct rect { int x1; int y1; int x2; int y2; int c; bool v; }; int main() { rect sheets[10001]; rect cur; int curTotal = 0; int A, B, N; //A = horizontal, B = vertical fstream infile, outfile; infile.open("rect1.in", ios::in); outfile.open("rect1.out", ios::out); infile >> A >> B >> N; sheets[0].x1 = 0; sheets[0].x2 = A; sheets[0].y1 = 0; sheets[0].y2 = B; sheets[0].c = 1; sheets[0].v = true; curTotal++; for (int i = 0; i < N; i++) { infile >> cur.x1 >> cur.y1 >> cur.x2 >> cur.y2 >> cur.c; //cout << cur.x1 << ' ' << cur.y1 << ' ' << cur.x2 << ' ' << cur.x2 << ' ' << cur.c << endl; for (int j = 0; j < curTotal; j++) { if (!sheets[j].v) continue; //check for simple cases(i.e intersect at a side) if (sheets[j].x1 < cur.x1 && sheets[j].x2 > cur.x1 && sheets[j].x2 <= cur.x2 && sheets[j].y1 >= cur.y1 && sheets[j].y2 <= cur.y2) { sheets[j].x2 = cur.x1; continue; } if (sheets[j].y1 < cur.y1 && sheets[j].y2 > cur.y1 && sheets[j].y2 <= cur.y2 && sheets[j].x1 >= cur.x1 && sheets[j].x2 <= cur.x2) { sheets[j].y2 = cur.y1; continue; } if (sheets[j].x2 > cur.x2 && sheets[j].x1 < cur.x2 && sheets[j].x1 >= cur.x1 && sheets[j].y1 >= cur.y1 && sheets[j].y2 <= cur.y2) { sheets[j].x1 = cur.x2; continue; } if (sheets[j].y2 > cur.y2 && sheets[j].y1 < cur.y2 && sheets[j].y1 >= cur.y1 && sheets[j].x1 >= cur.x1 && sheets[j].x2 <= cur.x2) { sheets[j].y1 = cur.y2; continue; } //check for intersections at corners //upper left corner if (sheets[j].x1 < cur.x1 && sheets[j].x2 > cur.x1 && sheets[j].y1 < cur.y1 && sheets[j].y2 > cur.y1 /*&& sheets[j].y2 < cur.y2*/) { sheets[curTotal].x1 = cur.x1; sheets[curTotal].y1 = sheets[j].y1; sheets[curTotal].x2 = sheets[j].x2; sheets [curTotal].y2 = sheets[j].y2; sheets[curTotal].c = sheets[j].c; sheets [curTotal].v = true; curTotal++; sheets[j].x2 = cur.x1; continue; } //upper right corner if (sheets[j].x2 > cur.x2 && sheets[j].x1 < cur.x2 && sheets[j].y1 < cur.y1 && sheets[j].y2 > cur.y1 /*&& sheets[j].y2 < cur.y2*/) Re: Weird Overlapping problem hi pal! i made my own algorithm for USACO and it makes 10 of 11 tests! these 10 tests are easy up to 1000x1000 but in the last there is the maximal data "10000 10000 1000" it's pretty cool!!! so i cheat a bit and i saw the output and then submit it back. got AC and when i so the SOLN my algorithm is good but not for huge tests over 1000x1000 and the code that fits uses the same method like yours. i don't have patience to correct sources! if you want the working code e-mail me and i'll send it to you! deal? zahari, bulgaria Re: Weird Overlapping problem Zahari can you give then working sorce from USACO,because i can't solve this problem from several months and i need this sorce.Please send me it to iliyan88@abv.bg |
|
|