10416 - Folding My T-Shirt

All about problems in Volume 104. 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
jaivasanth
New poster
Posts: 10
Joined: Tue Nov 26, 2002 4:19 pm

10416 - Folding My T-Shirt

Post by jaivasanth » Tue Nov 26, 2002 4:46 pm

I always get wrong answer ...

What i do is this....

1) I obtain only the corner points. For this i take 3 points at a time (continuos) and check the area of the triangle formed... if it is 0 i remove the middle point... i do this for all the points until i am left only with the points which are corners

2) Next i pick all possible combinations of pairs of points and get an axis of symmetry and use the mid point of these two points...
using this vector and the point i check to see if all other points have an image using this as the axis of symmetry . If such a pair exists. i break out and say "Yes". If not "No"

I really dont know whats wrong..

Please Help
Any test data that could fail my program ?

User avatar
kmhasan
Problemsetter
Posts: 107
Joined: Fri Oct 26, 2001 2:00 am
Location: Canada
Contact:

Post by kmhasan » Tue Nov 26, 2002 7:30 pm

My accepted solution says "No" for the following test case:
1
5
-2 0
0 2
2 0
1 0
0 0
Your program might say "Yes" as it'd remove the point (1,0).
I'm not sure if there is any test case in the judge data, though.

jaivasanth
New poster
Posts: 10
Joined: Tue Nov 26, 2002 4:19 pm

hi i removed that first portion of the code..........

Post by jaivasanth » Wed Nov 27, 2002 4:00 pm

yeah the test case you gave me failed my code... but then i removed that portion of the code that removed those intermediary points...
But how come...
Even if the T shirt folds properly ..... then all points need not overlap...

Anyway even after removing that portion my code fails with a wrong answer..

Can you send me your code..??

User avatar
kmhasan
Problemsetter
Posts: 107
Joined: Fri Oct 26, 2001 2:00 am
Location: Canada
Contact:

Post by kmhasan » Wed Nov 27, 2002 8:10 pm

Sure...

Mail me at <kmhasan@global-bd.net>. I'll reply with the code. There's no point posting the solution in the board and spoil others' spirit of solving it.

FlyDeath
Learning poster
Posts: 73
Joined: Wed Jan 02, 2002 2:00 am
Location: Taiwan

Post by FlyDeath » Sat Dec 14, 2002 2:52 pm

I use the other method.I thought it was right,but I always got WA.

My method is:
if there is A points.

1)If A is odd.Then I draw a line between every point n and the middle point of (n+(A-1)/2) and (n+(A-1)/2+1).Then check if it is OK.

2)If A is even.Then I draw a line between every point n and n+A/2,and check if it is OK or not.Then I draw a line between every middle point of n and n+1 and the middle point of (n+A/2) and (n+A/2+1).

Yarin
Problemsetter
Posts: 112
Joined: Tue Sep 10, 2002 5:06 am
Location: Ume
Contact:

Post by Yarin » Sun Dec 15, 2002 1:54 am

That's exactly what I'm doing (and I got AC), so I guess you must have made some error in the actual implemenation.

FlyDeath
Learning poster
Posts: 73
Joined: Wed Jan 02, 2002 2:00 am
Location: Taiwan

Post by FlyDeath » Mon Dec 16, 2002 3:17 pm

I really cant find the mistake :evil:.Can someone send me .exe file of this problem which can run under Windows XP?That way,I can use it for debugging.Really thanks.

I'll put my WA code below.Maybe someone will find the mistake :(

[cpp]
#include <stdio.h>
#include <math.h>
#define MAX 100

class point
{
public:
long x,y;
};

point all[MAX];

/* this is the function of checking if 2 points p3,p4 can match or not when I draw a line between p1 and p2 */
bool check(point p1,point p2,point p3,point p4)
{
long a=p1.y-p2.y;
long b=p1.x-p2.x;
if(b*(p3.x-p4.x)+a*(p3.y-p4.y)!=0)
return 1;
if(labs(a*p3.x+b*p3.y)!=labs(a*p4.x+b*p4.y))
return 1;
return 0;
}

void main()
{
int cases;
int nodes;
int i,j,k;
bool result;
point p1,p2;
scanf("%d",&cases);
for(k=0;k<cases;k++)
{
scanf("%d",&nodes);
for(i=0;i<nodes;i++)
{
scanf("%ld %ld",&all.x,&all.y);
all.x=all.x*2; /* I multiply it in order to avoid the situation of being floating point numbers */
all.y=all.y*2;
}
result=0;
if(nodes%2==0)
{
for(i=0;i<nodes;i++)
{
p1=all;
p2=all[(i+nodes/2)%nodes];
for(j=0;j<nodes/2;j++)
{
if(check(p1,p2,all[j],all[(nodes-j+i+i)%nodes])==1)
{
j=0;
break;
}
}
if(j!=0)
{
result=1;
break;
}
p1.x=(all.x+all[(i+1)%nodes].x)/2;
p1.y=(all.y+all[(i+1)%nodes].y)/2;
p2.x=(all[(i+nodes/2)%nodes].x+all[(i+nodes/2+1)%nodes].x)/2;
p2.y=(all[(i+nodes/2)%nodes].y+all[(i+nodes/2+1)%nodes].y)/2;
for(j=0;j<nodes/2;j++)
{
if(check(p1,p2,all[j],all[(nodes-j+i+i+1)%nodes])==1)
{
j=0;
break;
}
}
if(j!=0)
{
result=1;
break;
}
}
}
else
{
for(i=0;i<nodes;i++)
{
p1=all;
p2.x=(all[((nodes-1)/2+i)%nodes].x+all[((nodes-1)/2+i+1)%nodes].x)/2;
p2.y=(all[((nodes-1)/2+i)%nodes].y+all[((nodes-1)/2+i+1)%nodes].y)/2;
for(j=0;j<(nodes+1)/2;j++)
{
if(check(p1,p2,all[j],all[(nodes-j+i+i)%nodes])==1)
{
j=0;
break;
}
}
if(j!=0)
{
result=1;
break;
}
}
}
if(result==1)
printf("Yes\n");
else
printf("No\n");
}
}
[/cpp]

Caesum
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:

Post by Caesum » Mon Dec 16, 2002 8:55 pm

Code: Select all

if(labs(a*p3.x+b*p3.y)!=labs(a*p4.x+b*p4.y))
I would rethink this

FlyDeath
Learning poster
Posts: 73
Joined: Wed Jan 02, 2002 2:00 am
Location: Taiwan

Post by FlyDeath » Wed Dec 18, 2002 2:42 pm

oops.I found that error.(I made some mistake when I calculate this.)Really thank you :D .

Algoritmo
New poster
Posts: 32
Joined: Wed Oct 15, 2003 12:10 pm
Contact:

Post by Algoritmo » Sun Oct 26, 2003 10:30 am

I'm also getting WA. Here is my idea:

1) for all 3 consecutive points (such as 1,2,3 or last_point,0,1), verify if they are all in a straight line. If true, remove the 2nd one.
Note: The first of them (p1) goes from 0 to last_point, and does not move forward (p1++) if the point after him has just been removed. This ensures that all valid points will be checked.

2) for all 2 adjecent points (such as 0,1 or lastpoint,1), get A, B and C constants that define the line that passes right inbetween them (the bending line).
Note: This line is perpendicular to the line that can be traced with those 2 points.

3) if there is a even number of points, define also bending lines that pass through 2 opposing points (p2 = (p1+Points/2) % Points).

4) For each bending line, find all all pairs of p1 and p2, going clockwise for p1 and counter-clockwise for p2. Verify if they are equidistant from the bending line and if they trace a line that is perpendicular to the bending line. If there is any bending line that passes through this checking, answer is "Yes". Otherwise, answer is "No".

Formulas I used:
Defining the line that passes through p1 and p2:

Code: Select all

A = p2.y - p1.y;
B = p1.x - p2.x;
C = A*(p1.x) + B*(p1.y);
Verifying if p3 is in the line defined by A, B and C:

Code: Select all

if (C == A*(p3.x) + B*(p3.y)) return 1;
Verifying if 2 lines are parallel:

Code: Select all

if (A1*B2 == A2*B1) return 1;
Verifying if 2 lines are perpendicular:

Code: Select all

if (A1*A2 + B1*B2 == 0) return 1;
Verifying if p1 and p2 are equidistant from a line:

Code: Select all

if (A(p1.x + p2.x) + B(p1.y + p2.y) == C * 2) return 1;
I have used just integers and no division operation.

My program produces correct answers for the 4 test cases shown below, but there must be a test case in which my program fails. Please send me any different or tricky test cases. Thanks.
4
4
0 0
1 3
-2 4
-3 1
5
10 10
10 0
0 0
0 10
5 15
5
10 10
10 0
0 0
0 10
6 15
5
-2 0
0 2
2 0
1 0
0 0
Yes
Yes
No
Yes

Moha
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:

Incorrect testcase!

Post by Moha » Sun Aug 14, 2005 12:06 pm

Your testcases dosn`t obey the Counter clock wise order Rule, as stated in problem statement, so you can`t trust on them!!

crip121
New poster
Posts: 29
Joined: Tue Jul 08, 2008 9:04 pm

Re: 10416 - Folding My T-Shirt

Post by crip121 » Sun Oct 12, 2008 9:23 am

i thick test data of OJ's doesnt contain any colienear points.
i submit my code with considering remove colinear poing & not remove ; both ot AC.

crip121
New poster
Posts: 29
Joined: Tue Jul 08, 2008 9:04 pm

Re: 10416 - Folding My T-Shirt

Post by crip121 » Wed Oct 29, 2008 6:29 pm

i sorry about my previous post :oops: cause actually OJ's test data contains colinear points. and shockingly (remove) or (not remove) isnt any matter to solve this problem, both are lead to same ( & correct :) ) answer.

because my ac program (removing colinear points) is faster than the other. from my personal view i am shocked :o cause never expect this kind of situation from OJ, i have to think always that what can be the trick in test data. :lol: :lol:

hope this help for those are trying to solve :wink:

taufique
New poster
Posts: 3
Joined: Fri Nov 05, 2010 10:19 am

Re: 10416 - Folding My T-Shirt

Post by taufique » Wed Oct 05, 2011 6:21 pm

I don't know whether I am right or wrong but I think the judge test case has a mistake. as example consider the following test case:

1
10
3 0
2 1
-2 1
-1 0
-2 -1
-1 -3
-2 -4
2 -4
3 -3
2 -1

according to problem description I think this case should output "No". But probably in judge test case this kind of input wants output "Yes". This made me suffer much. May be I misunderstood, but is there anybody who can clear this confusion???

Post Reply

Return to “Volume 104 (10400-10499)”