convex hull sorting

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
sabir
New poster
Posts: 13
Joined: Thu Jun 14, 2007 8:48 am

convex hull sorting

Post by sabir »

i m having problem with my convex hull algo with sorting[/color].i get acc with this code 11096,218,10078 but get wrong ans many other.

my code is here.plz any one can help me to find bugs

int compare_point(const void *a, const void *b)
{
long xprod;
point *point_a, *point_b;

point_a=(point *)a;
point_b=(point *)b;

xprod=CrossProduct(Pivot, *point_a, *point_b);

if(xprod<0)
return 1;
else if(xprod>0)
return -1;
else
{
return 0;

double d1=distance(Pivot, *point_a);
double d2=distance(Pivot, *point_b);

if(d1>d2)
return (+1);
else
return (-1);
}
}

for colinear point i use distance;
following input my result is
input:
7
0 0
0 1
0 2
2 1
2 2
2 0
1 0
output
0, 0
2, 0
1, 0
2, 1
2, 2
0, 1
0, 2
but correct output may be(ant-clock dir)
0, 0
1, 0
2, 0
2, 1
2, 2
0, 2
0, 1

for any mistake and poor english i m sorry.

anjanpstu
New poster
Posts: 7
Joined: Thu Apr 07, 2011 8:40 am

getting wa always in 218

Post by anjanpstu »

I am getting wrong answer but can't find the problem.
here is my code
#include<stdio.h>
#include<math.h>
#include<vector>
using namespace std;
int main()
{
int n=0;float temp,temp1,temp2;int count=1;
float originpt,originpt1;double d,d1,d2;int c=0;double p;
float pta_x,pta_y,ptb_x,ptb_y;float sa;int d11=2;int r4=2;int r5,r6;double m1;float startpt;
vector<float>sr1;vector<float>sr2;vector<float>sr4;vector<float>v1;vector<float>v2;float length=0.00;float deb=0.0;
//freopen("acm218.in","rb",stdin);
while((scanf("%d",&n))==1)
{
length=0.00;
deb=0.0;
sr1.resize(n);sr2.resize(n);sr4.resize(n);

if(n==0)break;
else
{
for(int i=0;i<n;i++)
scanf("%f %f",&sr1,&sr2);
float min_x_coordinate=sr1[0];int anj=0;float min_y_coordinate=sr2[0];
for(int as=1;as<n;as++)
{
if(sr1[as]<min_x_coordinate)
{min_x_coordinate=sr1[as];min_y_coordinate=sr2[as];anj=as;}
else if(sr1[as]==min_x_coordinate&&sr2[as]<min_y_coordinate){min_x_coordinate=sr2[as];min_y_coordinate=sr2[as];anj=as;}

}
float min_x=sr1[anj];
float min_y=sr2[anj];
float min=sr2[0];int m=0;float min_x1=sr1[0];
for(int i=1;i<n;i++)
{
if(sr2<min){min=sr2;min_x1=sr1;m=i;}
else if(sr2==min&&sr1<min_x1){min=sr2;min_x1=sr1;m=i;}
}
float q=sr2[m];float q1=sr1[m];
sr2[m]=sr2[0];sr1[m]=sr1[0];
sr2[0]=q;sr1[0]=q1;
originpt=sr2[0];originpt1=sr1[0];
for(int i=1;i<n;i++)
{
double d=sr1-originpt1;
double d1=sr2[i]-originpt;
if(d==0&&d1==0)
{
m1=0;
p=(atan(m1)*360)/(2*3.1416);
sr4[i]=p;
}
else if(d>0&&d1>=0)
{
m1=d1/d;
if(m1<0)
{
p=(atan(m1)*360)/(2*3.1416);
p=360+p;
}
else if(m1>=0)
{
p=(atan(m1)*360)/(2*3.1416);
}
sr4[i]=p;
}

else if(d==0&&d1>0)
{
p=90;
sr4[i]=p;
}
else if(d==0&&d1<0)
{
p=90;
sr4[i]=p;
}
else if(d<0&&d1>0)
{
m1=d1/d;
if(m1<0)
{
p=(atan(m1)*360)/(2*3.1416);
p=360+p;
}
else if(m1>=0)
{
p=(atan(m1)*360)/(2*3.1416);
}
sr4[i]=p;
}
else if(d<0&&d1==0)
{
m1=0;
p=(atan(m1)*360)/(2*3.1416);
sr4[i]=p;
}
}
for(int i=1;i<n;i++)
{
for(int j=n-1;j>1;j--)
{
if(sr4[j]<sr4[j-1])
{

temp=sr4[j];
sr4[j]=sr4[j-1];
sr4[j-1]=temp;
temp1=sr1[j];
sr1[j]=sr1[j-1];
sr1[j-1]=temp1;
temp2=sr2[j];
sr2[j]=sr2[j-1];
sr2[j-1]=temp2;
}
else if(sr4[j]==sr4[j-1])
{deb=deb+1;
if(sr1[j-1]<sr1[j])
{

sr1[j-1]=sr1[j-1];
sr1[j]=sr1[j];

sr2[j-1]=sr2[j-1];
sr2[j]=sr2[j];

}
else if(sr1[j-1]>sr1[j])
{

temp1=sr1[j];
sr1[j]=sr1[j-1];
sr1[j-1]=temp1;


temp2=sr2[j];
sr2[j]=sr2[j-1];
sr2[j-1]=temp2;

}
}
}
}
v1.push_back(sr1[0]);v2.push_back(sr2[0]);
v1.push_back(sr1[1]);v2.push_back(sr2[1]);
if(n==2)
{
for(int j=v1.size()-1;j>0;j--)
length=length+(sqrt(((v1[j]-v1[j-1])*(v1[j]-v1[j-1]))+((v2[j]-v2[j-1])*(v2[j]-v2[j-1]))));
length=length+(sqrt(((v1[0]-v1[v1.size()-1])*(v1[0]-v1[v1.size()-1]))+((v2[0]-v2[v1.size()-1])*(v2[0]-v2[v1.size()-1]))));
printf("\n");
printf("Region #%d:\n",count);
for(int i=v1.size()-1;i>=0;i--)
{
printf("(%.1f,%.1f)-",v1[i],v2[i]);
}
printf("(%.1f,%.1f)",v1[v1.size()-1],v2[v1.size()-1]);
printf("\n");
printf("Perimeter length = %.2f\n",length);
count=count+1;
v1.clear();v2.clear();
sr1.clear();sr2.clear();

}
else
{
r4=2;d11=2;
for(int i=1;i<=n;i++)
{
for(int j=0;j<i;j++)
{
if(r4<n)
{
if(d11>=2)
{
pta_x=v1[d11-1]-v1[d11-2];
pta_y=v2[d11-1]-v2[d11-2];
ptb_x=sr1[r4]-v1[d11-2];
ptb_y=sr2[r4]-v2[d11-2];
sa=(pta_x*ptb_y)-(ptb_x*pta_y);
if(sa>=0.0)
{
v1.push_back(sr1[r4]);
v2.push_back(sr2[r4]);
r4=r4+1;d11=d11+1;
}

else if(sa<0.0)
{
if(d11>=2)
{
d11=d11-1;
v1.erase(v1.begin()+(d11));
v2.erase(v2.begin()+(d11));
}
if(d11==1)
{
v1.push_back(sr1[r4]);
v2.push_back(sr2[r4]);
}
}
}
}
}
}
for(int i=0;i<v1.size();i++)
{

if(v1[i]==min_x&&v2[i]==min_y){startpt=i;}
}
for(int j=v1.size()-1;j>0;j--)
length=length+(sqrt(((v1[j]-v1[j-1])*(v1[j]-v1[j-1]))+((v2[j]-v2[j-1])*(v2[j]-v2[j-1]))));
length=length+(sqrt(((v1[0]-v1[v1.size()-1])*(v1[0]-v1[v1.size()-1]))+((v2[0]-v2[v1.size()-1])*(v2[0]-v2[v1.size()-1]))));
printf("\n");
if(deb==n-1)
{
printf("Region #%d:\n",count);
for(int i=0;i<v1.size();i++)
printf("(%.1f,%.1f)-",v1[i],v2[i]);
printf("(%.1f,%.1f)",min_x,min_y);
printf("\n");
printf("Perimeter length = %.2f\n",length);
}
else
{
printf("Region #%d:\n",count);
printf("(%.1f,%.1f)-",min_x,min_y);
if(startpt!=0)
{
for(int i=startpt-1;i>=0;i--)
{
printf("(%.1f,%.1f)-",v1[i],v2[i]);
}

for(int i=v1.size()-1;i>=startpt+1;i--)
{
printf("(%.1f,%.1f)-",v1[i],v2[i]);
}
}
else if(startpt==0)
{
for(int i=v1.size()-1;i>0;i--)
{
printf("(%.1f,%.1f)-",v1[i],v2[i]);
}
}
printf("(%.1f,%.1f)",min_x,min_y);
printf("\n");
printf("Perimeter length = %.2f\n",length);
}
count=count+1;
v1.clear();v2.clear();
sr1.clear();sr2.clear();
}
}
}
}

Post Reply

Return to “Algorithms”