Question

SAlut ;)
Am nevoie de ajutor la acest tip de problema :
Este data o multime P = {P1, P2 ... Pn} formata din n puncte fiecare punct are coordonatele sale xj si yj
se cere un program care determina 3 puncte din multinea P pentru care Aria triughuiuui e maxima
Va rog frumos ajutatima

Answer 1

Cred ca tot metoda bruta este cea mai potrivita
Sa consideram ca avem 3 puncte a(x1,y1) b(x2,y2) si c(x0,y0)
Lungimea unui segment este determinata de expresia
$d(a,b)=ab=\sqrt{(y_{2}-y_{1})^{2}+(x_{2}-x_{1})^{2}}$ 
Pentru a afla distanta de la un punct la o dreapta, avem nevoie de panta m si deplasarea n cum apare in expresie
$y=m*x+n$ unde panta m pentru cele doua puncte a,b care ar apartine dreptei este egala cu
$m=frac{y_{2}-y_{1}}{x_{2}-x_{1}}$
Si atunci pentru unul dintre cele 2 puncte, sa zicem a(x1,y1) putem determina valoarea lui n
$n=y_{1}-m*x_{1}$
Atunci distanta de la c(x0,y0) la dreapta formata de a si b este
$d(c,ab)=h=\frac{|y_{0}-m*x_{0}-n|}{\sqrt{1+m^{2}}}$
Noi stim ca aria unui triunghi este baza*inaltime/2, dar pentru comparatia de arie ne trebuie decat partea de sus a fractiei
$A=h*ab$
Deci, am putea lua cate 2 puncte din sir si le tot asociem cu un al treilea punct de la care se va calcula distanta pana la segmentul format de cele 2 puncte si apoi aria respectiva este comparata cu cea maxima si daca este mai mare, se pastreaza cei 3 indici.

#include <iostream>
#include <fstream>
#include <cmath>
#include <cstring>
using namespace std;

//definim structura cu presupunerea
//ca punctele sunt intregi
struct Punct{
int x,y;
}puncte_fisier[100];
int nr_puncte;
//functie citire date
void citire(){
int i;
ifstream fid("date_puncte.txt");
fid>>nr_puncte;
for(i=0;i<nr_puncte;i++){
fid>>puncte_fisier[i].x>>puncte_fisier[i].y;
}
}
//aici determinam parametrii dreptei determinate de 2 puncte
//adica panta m, deplasarea n si lungimea segmentului determinat de puncte lung_seg
void param_dreapta(Punct p1,Punct p2,double &m,double &n,double &lung_seg){
m=(double)(p2.y-p1.y)/(p2.x-p1.x);
n=p1.y-m*p1.x;
lung_seg=sqrt((p2.y-p1.y)*(p2.y-p1.y)+(p2.x-p1.x)*(p2.x-p1.x));
}
//gasim mai intai distanta de la punctul p la dreapta determinata de m,n
//apoi prin inmultire cu lungimea segmentului, determinam dublul ariei de fat
double arie_triunghi(Punct p,double m,double n,double lung_seg){
double dist_punct_dreapta,arie;
dist_punct_dreapta=abs(p.y-m*p.x-n)/sqrt(1+m*m);
return lung_seg*dist_punct_dreapta;
}
//determinam indicii ariei maxime
void indici_arie_max(Punct p[],int &indici,double &arie_max){
int i,j,k;
double m,n,lung_seg,arie;
arie_max=0;
//pornind de la primele 2 luncte,
//determinam la fiecare parametri dreptei, si apoi aria care este formata
//cu un al treilea lunct
for(i=0;i<nr_puncte-2;i++){
for(j=i+1;j<nr_puncte-1;j++){
param_dreapta(p[i],p[j],m,n,lung_seg);
//daca in urma calculelor panta nu este infinita, se calculeaza aria cu al treilea punct
if(isinf(m)==0)
{
for(k=j+1;k<nr_puncte;k++){
arie=arie_triunghi(p[k],m,n,lung_seg);
//daca aria este mai mare decat cea maxima, atunci aria maxima devine aria actuala
//indicii sunt memorati intr-un numar de 3 cifre
if(arie>arie_max){
arie_max=arie;
indici=100*i+10*j+k;
}
}
}
//daca panta m este infinita, vom folosi punctele j si k pentru a determina parametrii dreptei
//si aflam distanta de la punctul i catre segmentul j,k
else{
for(k=j+1;k<nr_puncte;k++){
param_dreapta(p[j],p[k],m,n,lung_seg);
//daca m nu este infinit, gasim distanta de la i la segmentul determinat de j,k
if(isinf(m)==0){
arie=arie_triunghi(p[i],m,n,lung_seg);
if(arie>arie_max){
arie_max=arie;
indici=100*i+10*j+k;
}
}
//daca si acum panta este infinita, 3 puncte care determina aceeasi panta
//inseamna ca cele 3 puncte sunt coliniare, atunci aria este 0
else{
arie=0;
}
}
}
}
}
}

int main(){
int rez,i;
double arie_maxima;
citire();
indici_arie_max(puncte_fisier,rez,arie_maxima);
cout<<"Arie maxima este: "<<arie_maxima/2<<" pentru cele 3 puncte "<<rez/100+1<<" "<<(rez%100)/10+1<<" "<<rez%10+1;
return 0;
}