10556 - Biometrics

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

Moderator: Board moderators

Post Reply
Lain
New poster
Posts: 11
Joined: Sun Sep 21, 2003 5:45 pm
Location: Russia, PetrSU
Contact:

10556 - Biometrics

Post by Lain » Wed Oct 01, 2003 8:53 pm

Hi All!

To solve this problem I used assumption, that two poligons should have same angles between corresponding edges and have the same scale factor for all corresponding edge's lengths.
Does it right?

ditrix
New poster
Posts: 33
Joined: Sat Mar 01, 2003 12:38 am
Location: Paris

Post by ditrix » Thu Oct 02, 2003 2:43 am

yes, it's a basic idea, but you must also verify if the polygons has the same orientations. It means that you have to consider the angles from 0 to 180 deg as from 180 to 360 if the orientation is different.
@+!
DitriX

Lain
New poster
Posts: 11
Joined: Sun Sep 21, 2003 5:45 pm
Location: Russia, PetrSU
Contact:

Post by Lain » Thu Oct 02, 2003 11:47 pm

Sorry I don't get it! =(
It's said that "The vertices for both polygons correspond to the same set of features in the same order"

For examle we may have:
1poligon: right ear tip, chin cleft, right eye, nose, left eye, left ear tip, space between front teeth
2poligon: space between front teeth, right ear tip, chin cleft, right eye, nose, left eye, left ear tip

Can you give me example.

BiK
Experienced poster
Posts: 104
Joined: Tue Sep 23, 2003 5:49 pm

I also get WA on p10556

Post by BiK » Fri Oct 03, 2003 2:26 pm

I use the following idea: If the polygon's vertices are denoted by 1,2,3,...,n, then I chek if the triangles 123, 234, 345, ..., (n-2)(n-1)n, (n-1)n1, n12 are similar to the corresponding triangles in the second polygon. If this is the case, then I also check if the angles between the vectors 21 and 23, 32 and 34, 43 and 45, ..., n(n-1) and n1, and 1n and 12, have the same sign as their corresponding angles in the second polygon, thus checking if the polygons have the same orientation.

Is this correct? I keep receiving WA...

SM for BiK

Lain
New poster
Posts: 11
Joined: Sun Sep 21, 2003 5:45 pm
Location: Russia, PetrSU
Contact:

Post by Lain » Mon Oct 06, 2003 1:34 am

2ditrix:
I don't know why, but when I rewrote my program it's got AC.
I understood what were you talking about, but I haven't had that mistake.
I didn't use angles, I used sin and cos instead:

sin = vx1*vy2-vx2*vy1;
cos = vx1*vx2+vy1*vy2;
where vx1, vy1, vx2, vy2 - two standardized vectors

humaira
New poster
Posts: 1
Joined: Thu Mar 25, 2004 10:35 am
Location: Pakistan

10556 Biometric

Post by humaira » Thu Mar 25, 2004 10:59 am

1) Can anybody send me some critical inputs for this problem.
2) What is the criteria of scaling in the problem. whether the scaling would be done by fixing one particular point and then stretching the rest or whether it would be done with respect to a mid point.
3) Is it posible that a polygon is scaled first, translated to the third quardrant from the first quardrant and then reflected?

gvcormac
Problemsetter & Reviewer
Posts: 194
Joined: Fri Mar 15, 2002 2:00 am
Contact:

Post by gvcormac » Fri Mar 26, 2004 2:43 am

1) You can find the judges' data at plg.uwaterloo.ca/~acm00
2 & 3) I'm not sure I understand your questions, but I'll point out that when you do linear scaling, translation, and rotation, it doesn't make any difference what order you do them in.

Post Reply

Return to “Volume 105 (10500-10599)”