ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1147. Shaping Regions

Weird 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
Posted by nullman 4 Sep 2002 17:19
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
Posted by iliqn havov 31 Mar 2005 20:34
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