Привет всем.
Выкладываю код готовой программы:
Дано 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();
}
Можете задавать вопросы по коду....