## 209 - Triangular Vertices

Moderator: Board moderators

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

### 209 - Triangular Vertices

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

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

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

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]);
end;
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

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 )

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;

begin
verticecount := 0;
while not eoln do
begin
inc(verticecount);
with vertice[verticecount] do
begin
x := trunc(sqrt(1 + 8*(point - 1)) + 1) div 2;
y := point - x * (x - 1) div 2;
end;
end;
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
main;
end;
end.[/pascal]

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

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

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

give some critical inputs?
novice programmer