Cauta Drum Pana La Destinatie

[+skyler_sdf]

Datele de intrare se gasesc in fisierul "destinatie.in" sub forma: pe prima linie cele 4 coordonate reprezentand coordonatele punctului de pe drum, respectiv coordonatele destinatiei sub forma unor numere intregi, pe urmatoarele linii se afla coordonatele cate unui obstacol, dat prin: coordonatele varfului stanga-sus(x_sus, y_sus) si coordonatele punctului dreapta jos(x_jos, y_jos) tot sub forma unor numere intregi(presupunem ca obstacolele au laturile paralele si avem fixat un sistem de coordonate cu axele paralele cu aceste laturi ale dreptunghiurilor).

Datele de iesire: "destinatie.out" se va construi una dintre afirmatiile:

"Drumul nu se poate construi", resp. "Drumul se poate construi".

Problema se reduce de fapt la a determina daca un segment de dreapta intersecteaza un dreptunghi. Avem doua cazuri de analizat:

1. Daca segmentul este inclus intr.unul din semisegemtele de la stanga, de sus, de la dreapta sau de jos care nu includ dreptunghiul. Daca "da" (ambele capete sunt intr.unul din aceste semiplane), atunci decidem ca segmentul nu intersecteaza dreptunghiul.

2. Conditia ca in acest caz dreptunghiul si segmentul sa nu se intersecteze este ca toate varfurile dreptunghiului sa fie de aceeasi parte a dreptei determinate de segmentul dat.

#include<stdio.n>

FILE *fin;

typedef struc punct{

	int x, y;


}tpunct;

int max(int x, int y)

{


	return (x>y?x:y);

}

int caz1(tpunct d1, tpunct d2, tpunct s1, tpunct s2)

{

	int xsmax, xsmin, ysmax, ysmin;

	int xdmax, xdmin, ydmax, ydmin;

        xsmax=max(s1.x, s2.x);

	xsmin=min(s1.x, s2.x);

	ysmax=max(s1.y, s2.y);

	ysmin=min(s1.y, s2.y);

	xdmax=max(d1.x, d2.x);

	xdmin=min(d1.x, d2.x);

	ydmin=min(d1.y, d2.y);

	ydmax=max(d1.y, d2.y);

	return (xsmax<xdmin)|| (xsmin<xdmax) || (ysmin>ydmax) || (ysmin<ydmin);

}

int caz2(tpunct d1, tpunct d2, tpunct s1, tpunct s2)

{

double a, b, c;

double aux;

a=s1.y-s2.y;

b=s2.x-s1.x;

c=s1.x*s2.y-s2.x*s1.y;

return ((a*d2.x+b*d2.y+c)*aux>0)&&((a*d1.x+b*d1.y+c)*aux>0)&&((a*d2.x+b*d1.y+c)*aux>0);

}

int intersectie(tpunct d1, tpunct d2,tpunct s1, tpunct s2)

{


	if(caz1(d1, d2, s1, s2))

		return 0; //daca suntem in cazul 1

	if(caz2(d1, d2, s1, s2))

		return 0; //daca suntem in cazul 2

	return 1;

}

int citire_date(tpunct &m, tpunct &n)

{


	return fscanf(fin, "%d%d%d%d\n", &m.x, &m.y, &n.x, &n.y);

}

void scrie_date(int k)

{


	FILE *fout;

	fout=fopen("destinatie.out", "w");

	if(k)

		fprintf(fout, "Drumul nu se poate construi");

	else

		fprintf(fout, "Drumul se poate construi");

 fclose(fout);

}

void main()

{


	tpunct m, n;

	tpunct a, c;

	int verifica=0;

	fin=fopen("destinatie.out", "r");

	citire_date(m, n);

	while(citire_date(a, c)>1 && !verifica)

		verifica+=intersectie(a, c, m, n);

	scrie_date(verifica);

	fclose(fin);

}