Developing.ru

:shock: Привет всем

8) Помогите вот с такой задачей:

Дано 3n точек на плоскости, причем никакие 3 из них не лежат на 1ой прямой.
Построить множество n треугольников с вершинами в этих точках так, чтобы никакие 2 треугольника не пересекались и не содержали друг друга.

Вот то что я сделал:

Код: Выделить всё

#include <fstream.h>
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#define M 100
float x[M];
float y[M];
int i,j,k,n;
//----------------------------------------------------------//
int Chten()
{
 ifstream chten;
 chten.open("c:\\bc\\zadachi\\koor.txt");
 if (chten==NULL)
  {
   cout<<"error";
   return 0;
  }
 chten >> n;
 for (i=0;i<n;i++)
  {
   chten>>x[i];
   chten>>y[i];
  }
}
//-----------------------------------------------------------//
int proverka()
{
 for (i=0;i<n;i++){
 for (j=i;j<n;j++){
 for (k=j;k<n;k++){
 if ((x[j]-x[i])==0)   continue;
 if ((y[j]-y[i])==0)   continue;
 if ((k==j) || (i==j)) continue;
 if (((x[k]-x[i])/(x[j]-x[i]))-((y[k]-y[i])/(y[j]-y[i]))==0)
 {
  cout<<"error";
  return 0;
 }
}}}}
//===========================================================//
int main()
{
 clrscr();
 Chten();//чтение точек из файла//
 proverka();//чтобы никакие 3 точки не лежали на 1ой прямой//
 printf("\nX\n");//распечатка исходных точек//
 for (i=0;i<n;i++)
  {
   printf("%f",x[i]);
   printf("%c",i%2?'\t':'\n');
  }
 printf("\nY\n");
 for (i=0;i<n;i++)
  {
   printf("%f",y[i]);
   printf("%c",i%2?'\t':'\n');
  }
 getch();
}

8) Теперь надо:Построить множество n треугольников с вершинами в этих точках так, чтобы никакие 2 треугольника не пересекались и не содержали друг друга.

Помогите плз :shock:

Привет всем.

Выкладываю код готовой программы:

Дано 3n точек на плоскости, причем никакие 3 из них не лежат на 1ой прямой.
Построить множество n треугольников с вершинами в этих точках так, чтобы никакие 2 треугольника не пересекались и не содержали друг друга.

Все кому не лень, могут разобраться в коде, заодно ПРОТЕСТИРОВАТЬ и доложить мне об ошибке(я даже не прошу её исправлять,но надеюсь на это). Можете обсерать этот код - мне по..уй.
Код:

Код: Выделить всё

#include <fstream.h> 
#include <stdio.h> 
#include <stdlib.h> 
#include <conio.h> 
#include <math.h> 
#define M 50 
float x[M],y[M]; //координаты точек// 
int i,j,k,n,q,l=0,z[M],w=0,r; 
long double a,b,c,a1,b1,c1; 
long double p,p1,p2,p3,s,s1,s2,s3; 
float t[M][6];  //треугольники// 

//----------------------------------------------------------// 
int Chten() 
{ 
 ifstream chten; 
 chten.open("c:\\bc\\zadachi\\koor.txt"); 
 if (chten==NULL) 
  { 
   cout<<"error"; 
   return 0; 
  } 
 chten >> n; 
 for (i=0;i<n;i++) 
  { 
   chten>>x[i]; 
   chten>>y[i]; 
  } 
} 
//-----------------------------------------------------------// 
int proverka() 
{ 
 for (i=0;i<n;i++){ 
 for (j=i;j<n;j++){ 
 for (k=j;k<n;k++){ 
 if ((x[j]-x[i])==0)   continue; 
 if ((y[j]-y[i])==0)   continue; 
 if ((k==j) || (i==j)) continue; 
 if (((x[k]-x[i])/(x[j]-x[i]))-((y[k]-y[i])/(y[j]-y[i]))==0) 
 { 
  cout<<"error"; 
  getch(); 
  return 0; 
 } 
}}}} 
//-----------------------------------------------------------// 
float postr() 
{ 
  a=sqrt((x[j]-x[i])*(x[j]-x[i])+(y[j]-y[i])*(y[j]-y[i])); 
  b=sqrt((x[j]-x[k])*(x[j]-x[k])+(y[j]-y[k])*(y[j]-y[k])); 
  c=sqrt((x[i]-x[k])*(x[i]-x[k])+(y[i]-y[k])*(y[i]-y[k])); 
  p=(a+b+c)/2; 
  s=sqrt(p*(p-a)*(p-b)*(p-c)); 
  for (q=0;q<n;q++) 
  { 
   if ((q==i)||(q==k)||(q==j)) 
   continue; 
   a1=sqrt((x[k]-x[q])*(x[k]-x[q])+(y[k]-y[q])*(y[k]-y[q])); 
   b1=sqrt((x[j]-x[q])*(x[j]-x[q])+(y[j]-y[q])*(y[j]-y[q])); 
   c1=sqrt((x[i]-x[q])*(x[i]-x[q])+(y[i]-y[q])*(y[i]-y[q])); 

double  ca=(y[k]-y[j])*(x[q]-x[j]) - (y[q]-y[j])*(x[k]-x[j]); 
double  cb=(y[q]-y[j])*(x[q]-x[i]) - (y[q]-y[i])*(x[q]-x[j]); 
double  z =(y[k]-y[j])*(x[q]-x[i]) - (y[q]-y[i])*(x[k]-x[j]); 
double  ua; 
double  ub; 

           if (z!=0) 
                { ua=ca/z; 
                  ub=cb/z; } 
           else 
                { ua=ub=0; } 

  if ( (0<=ua)&&(ua<=1)&&(0<=ub)&&(ub<=1) ) 
  { 
   p1=(a1+b1+b)/2; 
   p2=(b1+c1+a)/2; 
   p3=(a1+c1+c)/2; 
   goto kor; 
  } 

        ca=(y[i]-y[j])*(x[q]-x[j]) - (y[q]-y[j])*(x[i]-x[j]); 
        cb=(y[q]-y[j])*(x[q]-x[k]) - (y[q]-y[k])*(x[q]-x[j]); 
        z =(y[i]-y[j])*(x[q]-x[k]) - (y[q]-y[k])*(x[i]-x[j]); 

        if (z!=0) 
                { ua=ca/z; 
                  ub=cb/z; } 
           else 
                { ua=ub=0; } 

  if ( (0<=ua)&&(ua<=1)&&(0<=ub)&&(ub<=1) ) 
  { 
   p1=(a1+b1+c)/2; 
   p2=(b1+c1+b)/2; 
   p3=(a1+c1+a)/2; 
   goto kor; 
  } 

        ca=(y[i]-y[j])*(x[q]-x[k]) - (y[q]-y[k])*(x[i]-x[j]); 
        cb=(y[q]-y[j])*(x[q]-x[i]) - (y[q]-y[i])*(x[q]-x[j]); 
        z =(y[i]-y[j])*(x[q]-x[i]) - (y[q]-y[i])*(x[i]-x[j]); 

        if (z!=0) 
                { ua=ca/z; 
                  ub=cb/z; } 
           else 
                { ua=ub=0; } 

  if ( (0<=ua)&&(ua<=1)&&(0<=ub)&&(ub<=1) ) 
  { 
   p1=(a1+b1+a)/2; 
   p2=(b1+c1+c)/2; 
   p3=(a1+c1+b)/2; 
   goto kor; 
  } 


       p1=(a1+b1+b)/2; 
       p2=(b1+c1+c)/2; 
       p3=(a1+c1+a)/2; 

kor:  s1=sqrt(p1*(p1-a1)*(p1-b1)*(p1-b)); 
      s2=sqrt(p2*(p2-b1)*(p2-c1)*(p2-c)); 
      s3=sqrt(p3*(p3-a1)*(p3-c1)*(p3-a)); 
   if (s==(s1+s2+s3)) return 0.0; 
  } 
    t[l][0]=x[i]; 
    t[l][1]=y[i]; 
     z[w]=i; 
     w=w+1; 
    t[l][2]=x[j]; 
    t[l][3]=y[j]; 
     z[w]=j; 
     w=w+1; 
    t[l][4]=x[k]; 
    t[l][5]=y[k]; 
     z[w]=k; 
     w=w+1; 
     l=l+1; 
    return 1.0; 
} 
//===========================================================// 
int main() 
{ 
 clrscr(); 
 z[0]=100;//главное чтобы z[i]!=0// 
 z[0]=100;//главное чтобы z[i]!=0// 
 Chten();//чтение точек из файла// 
 if (n%3!=0) {printf("error");getch();return 0;}//чтобы кол_во точек делилось 
 if (proverka()==0) return 0;//чтобы никакие 3 точки не лежали на 1ой прямой// 
  if (n==3)//если кол_во точек равно 3 то строим 1 теругольник и выходим// 
 { 
  t[0][0]=x[0]; 
  t[0][1]=y[0]; 
  t[0][2]=x[1]; 
  t[0][3]=y[1]; 
  t[0][4]=x[2]; 
  t[0][5]=y[2]; 
  goto kc; 
} 
 for (i=0;i<n;i++){  //строим тругольники!!!// 
 for (j=i;j<n;j++){ 
 for (k=j;k<n;k++){ 
 if ((i==j)||(j==k)||(k==i)) continue; 
 for (r=0;r<=w;r++)  //мы не берем координаты уже построенных треугольников// 
 { 
  if ((i==z[r])||(j==z[r])||(k==z[r])) goto as; 
 } 
 if (postr()==0.0) continue;//проверяем лежит ли точка внутри треугольника// 
as:; 
 }}} 
kc:printf("\nответ!!!\n");//распечатка координат треугольников// 
   for (i=0;i<l;i++) 
   { 
    printf("%d треугольник",(i+1)); 
   for (j=0;j<6;j++) 
   { 
    printf("%5.2f",t[i][j]); 
    if ((j%5==0)&&(j!=0)) printf("\n"); 
   } 
   } 
 getch(); 
}

Можете задавать вопросы по коду....

Developing.ru

Тругольники

Тругольники