209 - Triangular Vertices

All about problems in Volume 2. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Ivor
Experienced poster
Posts: 150
Joined: Wed Dec 26, 2001 2:00 am
Location: Tallinn, Estonia

209 - Triangular Vertices

Post by Ivor » Fri Apr 19, 2002 11:24 pm

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
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Fri Apr 19, 2002 11:49 pm

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
Experienced poster
Posts: 150
Joined: Wed Dec 26, 2001 2:00 am
Location: Tallinn, Estonia

Post by Ivor » Sat Apr 20, 2002 10:46 am

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
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Sun Apr 21, 2002 12:28 pm

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
Experienced poster
Posts: 150
Joined: Wed Dec 26, 2001 2:00 am
Location: Tallinn, Estonia

Post by Ivor » Sun Apr 21, 2002 12:47 pm

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
Experienced poster
Posts: 150
Joined: Wed Dec 26, 2001 2:00 am
Location: Tallinn, Estonia

Post by Ivor » Sun Apr 21, 2002 4:18 pm

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
Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia

209 Need help...

Post by Revenger » Wed Jun 12, 2002 7:16 pm

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
New poster
Posts: 15
Joined: Tue Sep 10, 2002 1:56 am
Location: Brasil
Contact:

Problem 209 - Big trouble

Post by Pedrinho UFPE » Tue Sep 10, 2002 2:05 am


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
Interested

lowai
New poster
Posts: 48
Joined: Mon Apr 29, 2002 1:26 pm

209 ( Triangular Vertices )

Post by lowai » Sat Nov 02, 2002 5:46 am

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
New poster
Posts: 48
Joined: Mon Apr 29, 2002 1:26 pm

Post by lowai » Sun Nov 03, 2002 2:48 pm

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
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Sun Nov 03, 2002 3:32 pm

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

lowai
New poster
Posts: 48
Joined: Mon Apr 29, 2002 1:26 pm

Post by lowai » Mon Nov 04, 2002 2:16 am

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

lowai
New poster
Posts: 48
Joined: Mon Apr 29, 2002 1:26 pm

Post by lowai » Mon Nov 04, 2002 2:17 am

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

ei01036
New poster
Posts: 12
Joined: Wed Jan 15, 2003 1:13 am

Post by ei01036 » Thu Feb 20, 2003 9:39 pm

I'm getting WA too...

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

is this correct?

samueljj
New poster
Posts: 18
Joined: Fri Jul 18, 2003 5:24 am

Critical input

Post by samueljj » Fri Jul 18, 2003 5:49 am

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

give some critical inputs?
novice programmer

Post Reply

Return to “Volume 2 (200-299)”