Из заданного мн-ва точек на плоскости выбрать 3 разные точки A,B,C так,чтобы внутри треугольника ABC было максимальное число точек

[Ronin94]

Из заданного мн-ва точек на плоскости выбрать 3 разные точки A,B,C так, чтобы внутри треугольника ABC содержалось максимальное кол-во точек этого мн-ва

[SAMOUCHKA]

а здесь что, форум математиков?

как определить- принадлежит ли точка треугольнику?

[Ronin94]

Надо прогу написать

[challengerr]

Пример на проверку принадлежности точки треугольнику

#include <stdio.h>
 
bool f(float x1,float y1,float x2,float y2,float x3,float y3,float x4,float y4)
{
float a1,b1,c1, a2,b2,c2, a3,b3,c3;
float r1,r2,r3;
// 1.x1,y1, x2,y2
a1 = y2 - y1;
b1 = x1 - x2;
c1 = x2*y1 - x1*y2;
 
r1 = a1*x3 + b1*y3 + c1;
r2 = a1*x4 + b1*y4 + c1;
r3 = r1*r2;
 
if (r3 < 0)
return false;
 
// 2.x2,y2, x3,y3
a2 = y3 - y2;
b2 = x2 - x3;
c2 = x3*y2 - x2*y3;
 
r1 = a2*x1 + b2*y1 + c2;
r2 = a2*x4 + b2*y4 + c2;
r3 = r1*r2;
 
if (r3 < 0)
return false;
 
 
// 3.x1,y1, x3,y3
 
a3 = y3 - y1;
b3 = x1 - x3;
c3 = x3*y1 - x1*y3;
 
r1 = a3*x2 + b3*y2 + c3;
r2 = a3*x4 + b3*y4 + c3;
r3 = r1*r2;
 
if (r3 < 0)
return false;
else
return true;
 
}
 
int main()
{
int r;
float x1,y1,x2,y2,x3,y3; // точки треугольника
float x4,y4; // проверяемая точка
 
x1 = 2.0;
y1 = 1.0;
 
x2 = 3.0;
y2 = 0.0;
 
x3 = -1.0;
y3 = 0.0;
 
x4 = 0.9;
y4 = 0.5;
 
r = f(x1,y1,x2,y2,x3,y3,x4,y4);
 
printf("%d\n", r);
 
return 0;
}

[magnet]

Сообщение от Ronin94

Надо прогу написать

Читай этот пост:
http://programmersforum.ru/showthread.php?t=34061