10416 - Folding My T-Shirt

[jaivasanth]

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 ?

[kmhasan]

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]

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]

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]

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]

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]

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]

Code: Select all

if(labs(a*p3.x+b*p3.y)!=labs(a*p4.x+b*p4.y))

I would rethink this

[FlyDeath]

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

[Algoritmo]

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]

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

[crip121]

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]

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]

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