588 - Video Surveillance

[mag]

Hi.

My algorithm for 588 works like this: for every wall I cut off the half plane at the back side of the wall from the resulting polygon. Then I check whether resulting polygon is empty. If it so, I say "impossible". Where I was wrong?

[horape]

Hi.

My algorithm for 588 works like this: for every wall I cut off the half plane at the back side of the wall from the resulting polygon. Then I check whether resulting polygon is empty. If it so, I say "impossible". Where I was wrong?

Almost correct, but the kernel can be a line or even a point, it need not to be a polygon with area > 0...

Code: Select all

+-------+
+       |
+----+xx+----+
     |       |
     +-------+

xx are valid positions for the camera but your program probably says it's impossible (if you've coded it the same way i did, change > by >=)

Saludos,
HoraPe

[kwedeer]

Here is mine code in Pascal. My strategy was the following - I am assuming that the region where the camare can be located is perfect rectangle (can be described by 4 numbers - minx, maxx, miny, maxy) - initially - the full plane and then this rectangle is reduced with the each new wall and at the end the comparison done:

Code: Select all

( (xmin>xmax) or
  (ymin>ymax)
            ) 

if true - then it is impossible to positionate the camera, if false - then it is not possible to do so. I have agreement with test case - but sadly - judge is giving WA.

Please, can someone go through my code and pick what is done wrong or can someone provide my test case for which my porgram fails to give correct answer. Any other hint is welcome.

I have taken into account the hint from previous post about equality and so on...

Thanks for any hints in advance!!

Code: Select all

program Prg5880(input, output);

{$APPTYPE CONSOLE}

uses
  SysUtils;

var
  inTask: boolean;
  numberOfWalls: Integer;
  x,y: array [1..100] of Integer;
  xmin,xmax: Integer;
  ymin,ymax: Integer;
  currDirection: Integer;
  currWallNumber: Integer;
  decided: Boolean;
  isPossible: Boolean;
  // 1 - up ->
  // 2 - right ->
  // 3 - down ->
  // 4 - left -> up...
  i: Integer;
  floorNumber: Integer;
begin
  {no more than 100 walls - so - each line will definitely serve as half-plane
   cut line. So - the only thing we must do: each time reduce the plane space - so -
   we should preserve only x-direction and y-direction intervals - it is easily seen
   that the camera positioning region always will be ractangle - the only thing is -
   decide which interval to reduce - x or y and which from 4 sides to cease. - so
   we should preserve the direction of the next wall for each of walls and
   this is sufficient.
   up,down,right,left
   up->only right
   right->only down
   down->only left
   left->only up
   so - decide which is the first direction...}

   {
  AssignFile(Input, 'in05__.txt');
  Reset(Input);
  AssignFile(Output, 'out05__.txt');
  Rewrite(Output);
    }
  floorNumber:=1; 
  inTask:=True;
  while inTask do begin

    xmin:=-1*MaxInt;
    xmax:=MaxInt;
    ymin:=-1*MaxInt;
    ymax:=MaxInt;
    read(numberOfWalls);
    //no optimization hear - one will have to read all the
    //lines anyway
    if (numberOfWalls>0) then begin
      for i:=1 to numberOfWalls do begin
        readln;
        read(x[i]);
        read(y[i]);
      end;
      //one of the following 4 will be evaluated definitely
      if y[2]>y[1] then currDirection:=1;
      if x[2]>x[1] then currdirection:=2;
      if y[2]<y[1] then currDirection:=3;
      if x[2]<x[1] then currDirection:=4;
      i:=2;
      decided:=False;
      isPossible:=False;
      while not decided do begin
        case currDirection of
          1: begin //up, so - the cutted domain is on the left:
               xmin:=x[i]; end;
          2: begin //right, so - the cutted domain is on top:
               ymax:=y[i]; end;
          3: begin //down, so - the cutted domain is on the right:
               xmax:=x[i]; end;
          4: begin //left, so - the cutted domain is on bottom:
               ymin:=y[i]; end;
        end; //case
        if ( (xmin>xmax) or
             (ymin>ymax)
            ) then begin
          decided:=True;
          isPossible:=False;
        end else begin //determine whether overlap ocurred
          //Determination of the new direction
          //One should take into account the last wall: numberOfWalls->1 as well
          if i=1 then begin
            decided:=True;
            isPossible:=True; //if loop is not interrupted then overlap is not detected
          end else if i=numberOfWalls then begin
            i:=1;
            if y[i]>y[numberOfWalls] then currDirection:=1;
            if x[i]>x[numberOfWalls] then currdirection:=2;
            if y[i]<y[numberOfWalls] then currDirection:=3;
            if x[i]<x[numberOfWalls] then currDirection:=4;
          end else begin
            inc(i);
            if y[i]>y[i-1] then currDirection:=1;
            if x[i]>x[i-1] then currdirection:=2;
            if y[i]<y[i-1] then currDirection:=3;
            if x[i]<x[i-1] then currDirection:=4;
          end;
        end; //determine whether overlap ocurred
      end; // while not Decided

      if floorNumber>1 then begin
        writeln;
      end;
      write('Floor #'+IntToStr(floorNumber));
      writeln;
      if isPossible then begin
        writeln('Surveillance is possible.');
      end else begin
        writeln('Surveillance is impossible.');
      end
     
    end else begin // if (numberOfWalls>0)
      inTask:=False;
    end; // if (numberOfWalls>0)

    inc(floorNumber);

  end; //while inTask

end.

[forthright48]

The points are given in clockwise order. So I try to find if the each point is on right or left compared to the previous two points ( like in convex hull ). If there are two points on left consecutively, it is impossible. Else possible. I am getting WA so probably my idea has flaws. Any cases where my idea fails?

Code: Select all

AC! Thanks brianfry713. Test case where my idea failed is given below.

[brianfry713]

It is possible if in the clockwise traversal, there exists no pair of vertical lines with one going down on the left of one going up and no pair of horizontal lines with one going left above one going right.

[forthright48]

Thanks brianfry713. My code was checking if there were consecutive lines that went against each other. Apparently, the pair of lines do not need to be consecutive. My code failed for the following test case:

Code: Select all

12
0 0
1 0
1 -1
4 -1
4 -2
3 -2
3 -3
2 -3
2 -2
-1 -2
-1 -1
0 -1

0

Answer: Surveillance is impossible.