273 - Jack Straws

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

[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

[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

[Adil]

Hello. my AC prog gives this output:

CONNECTED

hope this helps.

[Runtime_Error]

whats wrong with my code? i got WA after 0,184 sec working!
is there any trick in this problem?

help please

[Dmytro Chernysh]

Take a look at
http://www.csie.ntu.edu.tw/~b88062/acm/acmsource.html
and find the tests to this problem...

[Runtime_Error]

thanks for you help i got AC now

[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:

Code: Select all

CONNECTED
CONNECTED

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

[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

[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:)

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

[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;


}

[Jan]

Edit : My code was wrong!!!

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

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

Output:

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.

[Jan]

If you can find a common point in boh lines then you can say they are connected.