in this case it is not that complicated because there are only vertical and horizontal segments.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.
11106 - Rectilinear Polygon
Moderator: Board moderators
-
mukeshtiwari
- Learning poster
- Posts: 63
- Joined: Tue Mar 07, 2006 6:51 pm
- Location: india
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
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);
}
}
}
}You've made a wrong assumption.in my algorithm i assume that no three or more than 3 points will be collinear
In fact, even the sample input contains contains 4 collinear points; did you ever bother to check it?
That just rules out any kind of self-intersecting and self-touching polygons, and restricts inner angles to 90 or 270 degrees....as according to problem statement "each vertex is an endpoint of exactly one horizontal edge and one vertical edge "
-
mukeshtiwari
- Learning poster
- Posts: 63
- Joined: Tue Mar 07, 2006 6:51 pm
- Location: india
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 ....
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);
}
}
}
}