Cairn
BAN USERi=n-1;//global
struct node *construct(int post[],int in[],int n)
{
return const_post_in(post,in,0,n-1);
}
struct node * const_post_in(int post[],int in[],int s,int e)
{
int j;
if(s>e)
return NULL;
struct node *p=getnode();//allocate mem for node
p->info=post[i--];
for(j=s;in[j]!=post[i-1];j++)
;
p->r=const_post_in(post,in,j+1,e);
p->l=const_post_in(post,in,s,j-1);
return p;
}
Total no. of triangles possible : 360C3(i.e. (360*359*358)/6)
I think answers are:
For right angled triangle: 3/359(select a pair of pts.(end pts. of a diameter)in 180 ways and selecting the 3rd pt. in 358 ways. So, required probability is (180*358)/((360*359*358)/6) which is 3/359.
For acute: 178/359(select 1st pt. in 360 ways, 2nd in 358 and 3rd in 178(because pt opposite to 2nd pt. cannot be taken as well). Multiply all 3 and divide by 6(because ordering among pts. is not important))
For obtuse: 178/359(similar explanation as above)
for average case its O((n/2)log(k))
- Cairn January 28, 2012