Page 1 of 2
Incorrect problem description (probem 273)
Posted: Mon Feb 10, 2003 6:18 pm
by Jordan Gordeev
I think that the description of problem 273 is wrong.
It states that 1 < n < 13, but when I sent my solution, I received Runtime Error.
When I enlarged my arrays to hold more than 12 sticks, I got Wrong Answer.
Then I submitted a solution that would go into an endless loop if n is not between 1 and 13, and I got Time Limit Exceeded (the endless loop was entered).
It is also possible that the test data is incorrect, not the problem description.
Administrators' comments will be appreciated.
Posted: Tue Feb 11, 2003 8:51 am
by Dominik Michniewski
I don't think so ....
In my opinion IO for this problem is OK . But I don't know, do you see that is multiply input problem ? Maybe it's your problem Jordan ?
Dominik
273 - Jack Straws
Posted: Mon Mar 31, 2003 11:31 am
by eloha
I always got WA for this problem.
Please tell me the output for the follow input. Thanks.
Code: Select all
1
2
2 76 99 85
61 85 86 48
2 1
0 0
Posted: Mon Mar 31, 2003 6:39 pm
by Adil
Hello. my AC prog gives this output:
CONNECTED
hope this helps.
273 (Jack Straws)
Posted: Thu May 08, 2003 11:04 pm
by Runtime_Error
whats wrong with my code? i got WA after 0,184 sec working!
is there any trick in this problem?
help please
Here you are..
Posted: Fri May 09, 2003 12:22 am
by Dmytro Chernysh
Take a look at
http://www.csie.ntu.edu.tw/~b88062/acm/acmsource.html
and find the tests to this problem...
thank you
Posted: Sun May 11, 2003 10:54 pm
by Runtime_Error
thanks for you help
i got AC now
CAN'T UNDERSTAND
Posted: Tue Apr 18, 2006 6:40 am
by Jemerson
Hi guys, in the mentioned input above, which is the official one, there are some cases that my program just can't satisfy and i'm getting wrong answer all time.
I've already drawn the case and saw that the suggested output is impossible!
Can anyone please try this?
Code: Select all
1
8
2 76 99 85
62 96 29 98
8 2 64 50
95 87 16 72
8 90 43 9
61 90 87 20
83 6 34 89
61 85 86 48
4 2
6 2
The output suggested shows the following:
But it really doesn't make sense since line 2 has no connection with any other line! Can someone please help me?
Thanx in advance
273
Posted: Sat Jun 17, 2006 4:18 am
by asif_rahman0
thnx sohel vai... mone hoi i was sleeping
.
really stupid. so silly mistake.
have to do it by pencil and paper.
and also got it accepted
Posted: Sat Jun 17, 2006 7:23 pm
by asif_rahman0
can someone tell me now that am i correct about my theory or not??
just tell me.ok
otherwise i will be trouble in future.
so plz help me:)
pan - paper..
Posted: Sat Jun 17, 2006 9:18 pm
by sohel
You have two line segments:
L1 - (0, 0) - (2, 2)
L2 - (1, 1) - (3, 3)
Get a pen and a paper.
Draw these two line-segments with two different colored pens.
You will realize why these two intersect and hence why 1 and 2 are connected...
Hope it clears your confusion.
Could anyone check my code for me? for 273!!
Posted: Sat Oct 06, 2007 7:16 pm
by Hecton
I tested it with the inputs that I can find and all passed!
so what't wrong with it...Plz help! thx!
Code: Select all
#include <stdio.h>
#include <stdlib.h>
struct rod
{
int x1;
int y1;
int x2;
int y2;
};
struct rod t[13];
int map[13][13];
int main(void)
{
int dataset = 0;/* how many testing datasets*/
int rodnumber= 0;
int x = -1;
int y = -1;
int a=0,b=0,c=0;
int a1=0,b1=0,c1=0;
int i=0,j=0,k=0,h=0,t1=0,t2=0;
int u1=0,u2=0,u3=0,u4=0;
for (i = 0; i < 13; i++)
{
t[i].x1 = -1;
t[i].y1 = -1;
t[i].x2 = -1;
t[i].y2 = -1;
for (j = 0; j < 13; j++)
map[i][j] = -1;
}
scanf( "%d" , &dataset );
for (h = 0;h < dataset;h++)
{
/* initialization */
for (i = 0; i < 13; i++)
{
t[i].x1 = -1;
t[i].y1 = -1;
t[i].x2 = -1;
t[i].y2 = -1;
for (j = 0; j < 13; j++)
map[i][j] = 0;
}
scanf("%d",&rodnumber);
/* read in rod's coordinates*/
for (i = 0; i < rodnumber; i++)
scanf("%d %d %d %d",&t[i].x1,&t[i].y1,&t[i].x2,&t[i].y2);
/*set up connetion table*/
k = 0;j = 0; t1 = 0; t2 = 0;
for ( k = 0; k < rodnumber; k++)
{
/* see the relative positon of x,y of t[k] rod*/
a = -(t[k].x2 - t[k].x1);
b = t[k].y2 - t[k].y1;
c = (b*t[k].x1 + a*t[k].y1);
/*t[j] for checking, t[k] for ref. */
for ( j = 0; j < rodnumber; j++)
{
a1 = -(t[j].x2 - t[j].x1);
b1 = t[j].y2 - t[j].y1;
c1 = (b1*t[j].x1 + a1*t[j].y1);
t1 = (b*t[j].x1 + a*t[j].y1 - c)*(b*t[j].x2 + a*t[j].y2 - c);
t2 = (b1*t[k].x1 + a1*t[k].y1 - c1)*(b1*t[k].x2 + a1*t[k].y2 - c1);
u1 = (b*t[j].x1 + a*t[j].y1 - c);
u2 = (b*t[j].x2 + a*t[j].y2 - c);
/* t1: substitute t[j] into t[k]'s equation
t2: t[k] into t[j]'s equation
*/
if (t1 <= 0 && t2 <= 0) /*if on the line equation*/
{
/* two possible case: */
if ( t1 == 0 && t2 == 0)
{
if ( u1 == 0)
{
if (t[j].x1 < t[k].x1 && t[j].x1 < t[k].x2 && t[j].y1 < t[k].y1 && t[j].y1 < t[k].y2)
continue;
if (t[j].x1 > t[k].x1 && t[j].x1 > t[k].x2 && t[j].y1 > t[k].y1 && t[j].y1 > t[k].y2)
continue;
if (t[j].x1 == t[k].x1 && t[j].x2 == t[k].x2)
if ((t[j].y1 > t[k].y1 && t[j].y1 > t[k].y2) || (t[j].y1 < t[k].y1 && t[j].y1 < t[k].y2))
continue;
if (t[j].y1 == t[k].y1 && t[j].y2 == t[k].y2)
if ((t[j].x1 > t[k].x1 && t[j].x1 > t[k].x2) || (t[j].x1 < t[k].x1 && t[j].x1 < t[k].x2))
continue;
}
if (u2 == 0)
{
if (t[j].x2 < t[k].x1 && t[j].x2 < t[k].x2 && t[j].y2 < t[k].y1 && t[j].y2 < t[k].y2)
continue;
if (t[j].x2 > t[k].x1 && t[j].x2 > t[k].x2 && t[j].y2 > t[k].y1 && t[j].y2 > t[k].y2)
continue;
if (t[j].x1 == t[k].x1 && t[j].x2 == t[k].x2)
if ((t[j].y2 > t[k].y1 && t[j].y2 > t[k].y2) || (t[j].y2 < t[k].y1 && t[j].y2 < t[k].y2))
continue;
if (t[j].y1 == t[k].y1 && t[j].y2 == t[k].y2)
if ((t[j].x2 > t[k].x1 && t[j].x2 > t[k].x2) || t[j].x2 < t[k].x1 && t[j].x2 < t[k].x2)
continue;
}
}
/* make connection */
map[k][j] = 1;
map[j][k] = 1;
}
}
}
for( k=0 ; k<rodnumber ; ++k )
for( i=0 ; i<rodnumber ; ++i )
for( j=0 ; j<rodnumber ; ++j )
if( i!=j&&map[i][k]&&map[k][j] ) map[i][j] = 1 ;
while (1)
{
scanf("%d %d",&x,&y);
if (x == 0 && y == 0) break;
if (map[x-1][y-1])
puts( "CONNECTED" ) ;
else
puts( "NOT CONNECTED" ) ;
}/*outer while*/
if (h + 1) printf("\n");
}/*h for*/
/*}/*Most Outer while*/
return 0;
}
Posted: Sat Oct 06, 2007 10:15 pm
by Jan
Edit : My code was wrong!!!
Posted: Mon Oct 08, 2007 4:57 am
by Hecton
Sorry, I have a question. Line segment 6 overlaps all other line
segments. So the outputs should be "CONNECTED". Is that
ight? Or complete overlap of two lines does;nt constitue a
path to other line segments?
Jan wrote:Try the cases below:
Input:
Code: Select all
1
6
1 1 2 2
0 0 1 1
2 2 3 3
3 3 4 4
5 5 6 6
0 0 10 10
1 2
1 3
1 4
1 5
1 6
2 3
2 4
2 5
2 6
3 4
3 5
3 6
4 5
4 6
5 6
0 0
Code: Select all
CONNECTED
CONNECTED
CONNECTED
NOT CONNECTED
NOT CONNECTED
CONNECTED
CONNECTED
NOT CONNECTED
NOT CONNECTED
CONNECTED
NOT CONNECTED
NOT CONNECTED
NOT CONNECTED
NOT CONNECTED
NOT CONNECTED
Hope these help.
Posted: Mon Oct 08, 2007 10:03 am
by Jan
If you can find a common point in boh lines then you can say they are connected.