209 - Triangular Vertices

[Ivor]

What should I do if a point is on the side of an acceptable figure.
For example:
should I say that {7, 16, 11, 18} is a triangle or should I say it is not an acceptable figure.

Ivor

[Adrian Kuegel]

If a point is on the side of an acceptable figure, then it is not an acceptable figure. A triangle should have only 3 points, a parallelogram only 4 points and a hexagon only 6 points.
Do you check both possible directions of a parallelogram?

[Ivor]

If I got it right then there's actually three different orientations of a parallelogram, two for triangle and one for hexagon. Then I don't know what's wrong... I'll see if I can think of anything. Thanks anyway Adrian.

Ivor

[Adrian Kuegel]

You are right, I counted the two possible horizontal directions of the parallelogram as one. Do you calculate the row and the column in which the numbers are? With these values you can check easier if the give figure is acceptable or not

[Ivor]

Thanks, I got it accepted some 5 minutes ago.

I can't tell if it was the bug of my solution, but I have a deep suspicion that there's something wrong with the test data. I sent a mail asking for a bit of clarification -- just to clear the doubts.

Ivor

[Ivor]

Yepp, suspicion confirmed.

Somehow they had a '-' sign somewhere in the input. So beware of it until the next rejudgement -- last was 08/20/01.

Ivor

[Revenger]

There 2 types of triangle, 3 types of parallelogram and only 1 type of hexagon. I simply check them all. In any other cases I write that it's not an acceptable figure. But I get WA. Can anyone help me? There is my program:

[pascal](* Triangular Vertices *)

Program p209;

Const MaxN = 32767;
Message : Array[1..4]of String = (
'are the vertices of a triangle',
'are the vertices of a parallelogram',
'are the vertices of a hexagon',
'are not the vertices of an acceptable figure');

Var Inf : Array[1..MaxN] of Record Row,Col : Integer End;
list,l2 : Array[0..7]of Integer;
i,r,c : integer;
figure : integer;

Procedure MakeL2;
Var i,j,k : integer;
begin
for i:=0 to 6 do l2:=list;
for i:=1 to l2[0]-1 do
for j:=i+1 to l2[0] do
if l2>l2[j] then begin
k:=l2;
l2:=l2[j];
l2[j]:=k;
end;
end;

Procedure Check3;
Var a : Integer;
begin
figure:=4;
if Inf[l2[1]].Row=Inf[l2[2]].Row then begin
a:=Inf[l2[2]].Col-Inf[l2[1]].Col;
if Inf[l2[3]].Col<>Inf[l2[1]].Col then exit;
if Inf[l2[3]].Row-Inf[l2[1]].Row<>a then exit;
end else begin
if Inf[l2[2]].Row<>Inf[l2[3]].Row then exit;
a:=Inf[l2[3]].Col-Inf[l2[2]].Col;
if Inf[l2[2]].Col<>Inf[l2[1]].Col then exit;
if Inf[l2[2]].Row-Inf[l2[1]].Row<>a then exit;
end;
figure:=1;
end;

Procedure Check4;
Var a : Integer;
begin
figure:=4;
if Inf[l2[1]].Row=Inf[l2[2]].Row then begin
if Inf[l2[1]].Col=Inf[l2[3]].Col then begin
a:=Inf[l2[2]].Col-Inf[l2[1]].Col;
if Inf[l2[3]].Col<>Inf[l2[1]].Col then exit;
if Inf[l2[3]].Row-Inf[l2[1]].Row<>a then exit;
if Inf[l2[4]].Col<>Inf[l2[2]].Col then exit;
if Inf[l2[4]].Row-Inf[l2[2]].Row<>a then exit;
end else begin
if Inf[l2[2]].Col<>Inf[l2[3]].Col then exit;
a:=Inf[l2[2]].Col-Inf[l2[1]].Col;
if Inf[l2[3]].Col<>Inf[l2[2]].Col then exit;
if Inf[l2[3]].Row-Inf[l2[2]].Row<>a then exit;
if Inf[l2[4]].Col-a<>Inf[l2[2]].Col then exit;
if Inf[l2[4]].Row-Inf[l2[2]].Row<>a then exit;
end;
end else begin
if Inf[l2[2]].Row<>Inf[l2[3]].Row then exit;
a:=Inf[l2[3]].Col-Inf[l2[2]].Col;
if Inf[l2[2]].Col<>Inf[l2[1]].Col then exit;
if Inf[l2[2]].Row-Inf[l2[1]].Row<>a then exit;
if Inf[l2[4]].Col<>Inf[l2[3]].Col then exit;
if Inf[l2[4]].Row-Inf[l2[3]].Row<>a then exit;
end;
figure:=2;
end;

Procedure Check6;
Var a : Integer;
begin
figure:=4;
if Inf[l2[1]].Row<>Inf[l2[2]].Row then exit;
if Inf[l2[3]].Row<>Inf[l2[4]].Row then exit;
if Inf[l2[5]].Row<>Inf[l2[6]].Row then exit;
a:=Inf[l2[2]].Col-Inf[l2[1]].Col;
if Inf[l2[3]].Col<>Inf[l2[1]].Col then exit;
if Inf[l2[3]].Row-Inf[l2[1]].Row<>a then exit;
if Inf[l2[4]].Col-a<>Inf[l2[2]].Col then exit;
if Inf[l2[4]].Row-Inf[l2[1]].Row<>a then exit;
if Inf[l2[5]].Col-a<>Inf[l2[3]].Col then exit;
if Inf[l2[5]].Row-Inf[l2[3]].Row<>a then exit;
if Inf[l2[6]].Col<>Inf[l2[4]].Col then exit;
if Inf[l2[6]].Row-Inf[l2[4]].Row<>a then exit;
figure:=3;
end;

begin
Inf[1].Row:=1;
Inf[1].Col:=1;
r:=1;
c:=1;
for i:=2 to MaxN do begin
if c=r then begin
inc(r);
c:=1;
end else
inc(c);
Inf.Row:=r;
Inf.Col:=c;
end;
While Not Eof(InPut) Do begin
list[0]:=0;
While Not Eoln(InPut) Do begin
Inc(list[0]);
Read(list[list[0]]);
end;
if Eoln(InPut) then Readln;
MakeL2;
Case list[0] of
3 : Check3;
4 : Check4;
6 : Check6;
else figure:=4;
end;
for i:=1 to list[0] do Write(list,' ');
Writeln(Message[figure]);
end;
end.[/pascal]

[Pedrinho UFPE]

Hi people!
Thanks for Ivor and Adrian Kougel for the interesting commentaries about this problem. But, I'm here to tell that a shape like {2,5,3,6,8,9} should be accepted, the problem dont wanna a "regular convex" hexagon. At least the problem statment don't tell anything about it.

/ /
\ \

Another thing is that i did the problem converting the k-coordinate (the label of the point in a grid) to (x,y)-real coordinate system. But I still having WA. Maybe I suppose that the figure above is an acceptable one and it is false.

Bye! Good luck for next problems

[lowai]

why does this code get WA? Any tricks in this problem?

[pascal]
const figurecount = 6;
type
toutline = array[1..6, 1..2]of byte;
tfigure = record
outline : toutline;
verticecount : byte;
name : string[20];
end;
tvertice = record
point, x, y : word;
end;
const
figure : array[1..figurecount]of tfigure = (
(Outline:((0,0),(0,1),(1,1),(0,0),(0,0),(0,0)); Verticecount:3; Name:'triangle'),
(Outline:((0,0),(1,0),(1,1),(0,0),(0,0),(0,0)); Verticecount:3; Name:'triangle'),
(Outline:((0,0),(1,0),(1,1),(2,1),(0,0),(0,0)); Verticecount:4; Name:'parallelogram'),
(Outline:((0,0),(0,1),(1,1),(1,2),(0,0),(0,0)); Verticecount:4; Name:'parallelogram'),
(Outline:((0,0),(0,1),(1,0),(1,1),(0,0),(0,0)); Verticecount:4; Name:'parallelogram'),
(Outline:((0,0),(0,1),(1,0),(1,2),(2,1),(2,2)); Verticecount:6; Name:'hexagon'));
var
verticecount : integer;
vertice : array[0..20]of tvertice;

procedure readdata;
begin
verticecount := 0;
while not eoln do
begin
inc(verticecount);
with vertice[verticecount] do
begin
read(point);
x := trunc(sqrt(1 + 8*(point - 1)) + 1) div 2;
y := point - x * (x - 1) div 2;
end;
end;
readln;
end;

procedure main;
var i, j, k : integer;
ratio : word;
b : boolean;
begin
for k := 1 to verticecount do
write(vertice[k].point, ' ');
for i := 1 to verticecount - 1 do
for j := i + 1 to verticecount do
if vertice.point > vertice[j].point then
begin
vertice[0] := vertice;
vertice := vertice[j];
vertice[j] := vertice[0];
end;
for k := verticecount downto 1 do
begin
dec(vertice[k].x, vertice[1].x);
dec(vertice[k].y, vertice[1].y);
end;

b := false;
for k := 1 to figurecount do
if figure[k].verticecount = verticecount then
with figure[k] do
begin
i := 1;
while outline[i, 1] = 0 do inc(i);
ratio := vertice.x div outline[i, 1];
b := true;
for i := 2 to verticecount do
if (vertice.x <> outline[i, 1] * ratio) or
(vertice.y <> outline[i, 2] * ratio) then
begin b := false; break; end;
if b then break;
end;
if b then
writeln('are the vertices of a ', figure[k].name)
else
writeln('are not the vertices of an acceptable figure');
end;

begin
while not eof do
begin
readdata;
main;
end;
end.[/pascal]

[lowai]

After reading another message with the same problem id, it said the hexagon is not always regular. so I changed the head of the code:
[pascal]
const
figurecount = 14;
type
toutline = array[1..6, 1..2]of shortint;
tfigure = record
outline : toutline;
verticecount : byte;
name : string[20];
end;
tvertice = record
point, x, y : longint;
end;
const
figure : array[1..figurecount]of tfigure = (
(Outline:((0,0),(0,1),(1,1),(0,0),(0,0),(0,0)); Verticecount:3; Name:'triangle'),
(Outline:((0,0),(1,0),(1,1),(0,0),(0,0),(0,0)); Verticecount:3; Name:'triangle'),
(Outline:((0,0),(1,0),(1,1),(2,1),(0,0),(0,0)); Verticecount:4; Name:'parallelogram'),
(Outline:((0,0),(0,1),(1,1),(1,2),(0,0),(0,0)); Verticecount:4; Name:'parallelogram'),
(Outline:((0,0),(0,1),(1,0),(1,1),(0,0),(0,0)); Verticecount:4; Name:'parallelogram'),
(Outline:((0,0),(0,1),(1,0),(1,2),(2,1),(2,2)); Verticecount:6; Name:'hexagon'),
(Outline:((0,0),(0,1),(1,0),(1,1),(2,1),(2,2)); Verticecount:6; Name:'hexagon'),
(Outline:((0,0),(0,1),(1,1),(1,2),(2,1),(2,2)); Verticecount:6; Name:'hexagon'),
(Outline:((0,0),(1,0),(1,1),(1,2),(2,1),(2,2)); Verticecount:6; Name:'hexagon'),
(Outline:((0,0),(1,-1),(1,0),(1,1),(2,0),(2,1)); Verticecount:6; Name:'hexagon'),
(Outline:((0,0),(0,1),(1,0),(1,1),(2,0),(2,1)); Verticecount:6; Name:'hexagon'),
(Outline:((0,0),(0,1),(1,1),(1,2),(2,2),(2,3)); Verticecount:6; Name:'hexagon'),
(Outline:((0,0),(0,1),(0,2),(1,1),(1,2),(1,3)); Verticecount:6; Name:'hexagon'),
(Outline:((0,0),(0,1),(0,2),(1,0),(1,1),(1,2)); Verticecount:6; Name:'hexagon'));
[/pascal]
but i still get WA.

[Adrian Kuegel]

The hexagon has to be regular. That means there exist only one orientation of a hexagon.

[lowai]

well, i changed it back to what it was.
Still get WA. Could anyone provide me some test data?

[lowai]

well, i changed it back to what it was.
Still get WA. Could anyone provide me some test data?

[ei01036]

I'm getting WA too...

My program analises:
2 different triangle types;
3 different paralelogram types;
1 hexagon type;

is this correct?

[samueljj]

[quote="ei01036"]I'm getting WA too...

give some critical inputs?