Page 1 of 1
588 - Video Surveillance
Posted: Fri Nov 08, 2002 2:39 pm
by 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?
Re: 588 WA
Posted: Fri Dec 05, 2003 6:05 am
by horape
mag wrote: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
Posted: Thu Sep 21, 2006 8:12 pm
by 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:
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.
Re: 588 WA
Posted: Tue Jan 22, 2013 6:55 pm
by 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.
Re: 588 WA
Posted: Tue Jan 22, 2013 11:57 pm
by 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.
Re: 588 WA
Posted: Thu Jan 24, 2013 11:37 am
by 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.