## 10416 - Folding My T-Shirt

Moderator: Board moderators

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

### 10416 - Folding My T-Shirt

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..

Any test data that could fail my program ?

kmhasan
Problemsetter
Posts: 107
Joined: Fri Oct 26, 2001 2:00 am
Contact:
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..........

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..??

kmhasan
Problemsetter
Posts: 107
Joined: Fri Oct 26, 2001 2:00 am
Contact:
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
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:
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
I really cant find the mistake .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:

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
oops.I found that error.(I made some mistake when I calculate this.)Really thank you .

Algoritmo
New poster
Posts: 32
Joined: Wed Oct 15, 2003 12:10 pm
Contact:
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!

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

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

i sorry about my previous post 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 cause never expect this kind of situation from OJ, i have to think always that what can be the trick in test data.  hope this help for those are trying to solve taufique
New poster
Posts: 3
Joined: Fri Nov 05, 2010 10:19 am

### Re: 10416 - Folding My T-Shirt

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???