OJ Board

Posted: **Sat Nov 18, 2006 10:17 pm**

gvcormac wrote: If you insist on implementing the problem as specified, you have to worry about segment intersection. There are algorithms for this but sub-quadratic is complicated.

in this case it is not that complicated because there are only vertical and horizontal segments.

Posted: **Mon Jan 22, 2007 9:54 pm**

hi ...
i tried to slove this problem but failed .plz help me
my algorithm is
first i m trying to find out starting point having minimum x .if we have two x similar than starting point will be the point having minimun y. so i get starting point .
now i make a loop . there must be a point in the list( remaining n-1 points) which has same x coordinate as of starting point .so this will be my second point .for 3rd point there must be a point in the remaining list(n-2 points) whose y coordinate must be equal to y coordinate of 2nd point .
for example if (x,y) is starting point then second point will be (x,w) ,third point will be (z,w) ,4th point will be (z,v).....and so on . now inorder to find out wheather the polygon is simple or not ....my algo is
suppose there r 8 points in the list . i sorted 3 points based on above algorithm and now i m on 4th point . now i compare y cordianate of 4th point from the y coordiante of all the remaining points( 5th ,6th ,7th ,8th) . now if none of the remaining points have same y it means that these remaining points r not horizontal to 4th point . so polygon is not simple ... and in this case i printed -1;
in my algorithm i assume that no three or more than 3 points will be collinear ...as according to problem statement "each vertex is an endpoint of exactly one horizontal edge and one vertical edge "

a given input ..
0 0
0 2
2 0
2 2
1 1
1 3
3 1
3 3
applying the above algorithm ..
my stating points is 0 0
second points is 0 2
3rd is 2 2
4th is 2 0
now there are no points whose y is equal to y coordinate of 4th point( 2 0)
so polygon is not simple ...
and i printed -1
plz tell me my algorithm is correct or not ..
or i did not understand the problem ....plz help me ..

here is mycode

Code: Select all

#include<stdio.h>
#include<math.h>
    main()
     {
        int m,n,a,x[100010],v,y[100010],temp1,temp2,i,j,flag,count;
        scanf("%d",&m);
        for(v=0;v<m;v++)
        {
            scanf("%d",&n);
            for(j=0;j<n;j++)
             scanf("%d%d",&x[j],&y[j]);
             if(n%2!=0)
                printf("-1\n");//if number of points is odd
             else
                 {
                i=0;
                for(j=1;j<n;j++)
                  {
                    if(x[i]>x[j])
                     {               
                        temp1=x[i];
                        temp2=y[i];
                        x[i]=x[j];
                        y[i]=y[j];
                        x[j]=temp1;
                        y[j]=temp2;
                     }
                    else if(x[i]==x[j])
                     {
                        if(y[i]>y[j])
                         {
                             temp1=x[i];
                                                     temp2=y[i];
                                                     x[i]=x[j];
                                                        y[i]=y[j];
                                                        x[j]=temp1;
                                                        y[j]=temp2;   
                         }
                     }
                   }//min coordiante will be in x[0],y[0]
                //printf("%d %d\n",x[0],y[0]);
           
                flag=0;
                count=1;
                for(i=0;i<n-1;i++)//sorting process of remaining n-1 points
                 {
                    for(j=i+1;j<n;j++)
                     {
                        if(i%2==0)
                         {
                            if(x[i]==x[j])//compare x coordiante
                              {
                                temp1=x[i+1];
                                temp2=y[i+1];
                                x[i+1]=x[j];
                                y[i+1]=y[j];
                                x[j]=temp1;
                                y[j]=temp2;
                                flag=1;
                                count++;
                                break;               
                              }
                           
                         }
                         
       
                         else if(i%2!=0)
                          {
                            if(y[i]==y[j])//compare y coordiante
                             {
                                temp1=x[i+1];
                                                                temp2=y[i+1];
                                                                x[i+1]=x[j];
                                                                y[i+1]=y[j];
                                                                x[j]=temp1;
                                                                y[j]=temp2;
                                                                flag=1;
                                count++;
                                                                break;       
                             }
                           
                          }
                     }
                    if(!flag)// could not find points in the remaing list whose x coordiante is equal to x[i] or y coordiante is equal to y[i] so pplygon is not simple
                        {
                            printf("-1\n");
                            flag=1;
                            break;
                        }
                    flag=0;//initialization of flag again
                 }
            /*printf("points in sorted order\n");
            for(i=0;i<n;i++)
              printf("%d %d\n",x[i],y[i]);
            printf("count=%d\n",count);*/
            double  sum=0;
            if(!flag)
             {
            for(i=0;i<n;i++)
            sum=sum+sqrt((x[i%n]-x[(i+1)%n])*(x[i%n]-x[(i+1)%n]) + ((y[i%n]-y[(i+1)%n]))*((y[i%n]-y[(i+1)%n])) );
            printf("%.0lf\n",sum);
             }
            }           
        }
    }

Posted: **Mon Jan 22, 2007 11:44 pm**

in my algorithm i assume that no three or more than 3 points will be collinear

You've made a wrong assumption.
In fact, even the sample input contains contains 4 collinear points; did you ever bother to check it?

...as according to problem statement "each vertex is an endpoint of exactly one horizontal edge and one vertical edge "

That just rules out any kind of self-intersecting and self-touching polygons, and restricts inner angles to 90 or 270 degrees.

Posted: **Mon Jan 29, 2007 3:26 pm**

hi now i have changed my algorithm but still getting WA .first i m trying to find out starting point having minimum x .if we have two x similar than starting point will be the point having minimun y. so i get starting point .so i store minimum point in x[0] and y[0].now there r remaining n-1 points in the array. i try to find out second point by searching through list of n-1 remaining points . second point will be that points whose x coordinate will be same as first point ( x[0] ,y[0]) .if there r more than 2 points having same x coordinate then i select that point whose difference ( abs(y[0]-y[j]) is minimum with current point (x[0] ,y[0]).point having minimum difference will be nearer to point (x[0],y[0]) .so found second point(x[1],y[1]). now same approach i apply for 3rd and other points of the list .
now in order to find that polygon is simple or not
at any point of sorting if i m not able to find the correspoinding point of point it means that polygon is not simple....

suppose there are 8 points in the list . i sorted 3 points based on above algorithm and now i m on 4th point . now i compare y cordianate of 4th point from the y coordiante of all the remaining points( 5th ,6th ,7th ,8th) . now if none of the remaining points have same y it means that these remaining points r not horizontal to 4th point . so polygon is not simple ... and in this case i printed -1;
here is my code ....

Code: Select all

#include<stdio.h>
#include<math.h>
#include<stdlib.h>
	main()
	 {
		int m,n,a,x[100010],v,y[100010],temp1,temp2,i,j,flag,count;
		scanf("%d",&m);
		for(v=0;v<m;v++)
		{
			scanf("%d",&n);
			for(j=0;j<n;j++)
			 scanf("%d%d",&x[j],&y[j]);
			 if(n%2!=0)
				printf("-1\n");//if number of points is odd 
			 else
			     {
				i=0;
				for(j=1;j<n;j++)
				  {
					if(x[i]>x[j])
					 {				
						temp1=x[i];
						temp2=y[i];
						x[i]=x[j];
						y[i]=y[j];
						x[j]=temp1;
						y[j]=temp2;
					 }
					else if(x[i]==x[j])
					 {
						if(y[i]>y[j])
						 {
							 temp1=x[i];
                                                	 temp2=y[i];
                                                	 x[i]=x[j];
                                               		 y[i]=y[j];
                                               		 x[j]=temp1;
                                               		 y[j]=temp2;	
						 }
					 }
			 	  }//min coordiante will be in x[0],y[0]
				//printf("%d %d\n",x[0],y[0]);
			
				flag=0;
				count=1;
			        int min,min1;
				int k,k1,flag1=1,flag2;
				for(i=0;i<n-1;i++)//sorting process of remaining n-1 points
				 {
					//min=min1=999999;
					flag2=1;
					for(j=i+1;j<n;j++)
					 {
						if(i%2==0)
						 {
							
							if(x[i]==x[j])//compare x coordiante 
							  {
								if(flag2)
								{
								 min=abs(y[i]-y[j]);
								 //printf("j=%d min=%d\n",j,min);
								 temp1=x[i+1];
                                                                 temp2=y[i+1];
                                                                 x[i+1]=x[j];
                                                                 y[i+1]=y[j];
                                                                 x[j]=temp1;
                                                                 y[j]=temp2;
                                                                 flag=1;
								 flag2=0;
								}
								else 
								 {
									k=abs(y[i]-y[j]);
									//printf("min=%d k=%d\n",min,k);
									if(min>k)
									{
										min=k;
										temp1=x[i+1];
										temp2=y[i+1];
										x[i+1]=x[j];
										y[i+1]=y[j];
										x[j]=temp1;
										y[j]=temp2;
										flag=1;
									}
								 }
												
							  }
							
						 }
						 
		
						 else if(i%2!=0)
						  {
							if(y[i]==y[j])//compare y coordiante
							 {
								if(flag2)
								 {
									min1=abs(x[i]-x[j]);
									//printf("j=%d min1=%d\n",j,min1);
									temp1=x[i+1];
                                                                        temp2=y[i+1];
                                                                        x[i+1]=x[j];
                                                                        y[i+1]=y[j];
                                                                        x[j]=temp1;
                                                                        y[j]=temp2;
                                                                        flag=1;
									flag2=0;
								 }
								else 
								 {
									k1=abs(x[i]-x[j]);
									//printf("k1=%d min1=%d\n",k1,min1);
									if(min1>k1)
								 	{
										min1=k1;
										temp1=x[i+1];
                                                                		temp2=y[i+1];
                                                                		x[i+1]=x[j];
                                                                		y[i+1]=y[j];
                                                                		x[j]=temp1;
                                                                		y[j]=temp2;
										flag=1;		
							 		}
								 }
							
						  	}
					 	}
					
				      }
					if(!flag)//not found the corresponding point in the list 
						{
							printf("-1\n");
							flag1=0;
							break;
						}
					flag=0;//initalization...
			      }
			/*printf("points in sorted order\n");
			for(i=0;i<n;i++)
			  printf("%d %d\n",x[i],y[i]);
			//printf("count=%d\n",count);*/
			double  sum=0;
			if(flag1)
			 {
			for(i=0;i<n;i++)
			sum=sum+sqrt((x[i%n]-x[(i+1)%n])*(x[i%n]-x[(i+1)%n]) + ((y[i%n]-y[(i+1)%n]))*((y[i%n]-y[(i+1)%n])) );
			printf("%.0lf\n",sum);
			 }
		     }
		    			
		}
	}

OJ Board

11106 - Rectilinear Polygon