Cod sursa(job #338589)

Utilizator AndreiDDiaconeasa Andrei AndreiD Data 6 august 2009 11:40:23
Problema Oypara Scor 10
Compilator cpp Status done
Runda Lista lui wefgef Marime 1.41 kb
#include <cstdio>
#include <cstring>

#define file_in "oypara.in"
#define file_out "oypara.out"

#define Nmax 100100
#define Inf 0x3f3f3f3f

int x[2*Nmax];
int y[2*Nmax];
int n,nri,okk,ok,i,j,k,xx,yy1,yy2,ind1,ind2;


int inter(int a, int b, int c)
{
	double p1,p2,p3,aux;
	//ab
	if (x[a]==x[b])
		p1=Inf;
	else
		//calculez panta (Yb-Ya)/(Xb-Xa)
		p1=(y[b]-y[a])/(x[b]-x[a]);
	//ac	
	if (x[a]==x[c])
		p2=Inf;
	else
		//calculez panta (Yc-Ya)/(Xc-Xa)
		p2=(y[c]-y[a])/(x[c]-x[a]);
	if (x[a]==x[c+n])
		p3=Inf;
	else
		//calculez panta (Yc+n-Ya)/(Xc+n-Xa)
		p3=(y[c+n]-y[a])/(x[c+n]-x[a]);
	if (p2>p3)//swap
	{
		aux=p2;
		p2=p3;
		p3=aux;
	}
	
	if (((p2==Inf) && (p3==Inf)) || ((p1>=p2) && (p1<=p3)))
		return 1;
	
	return 0;
}


	

int main()
{
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	scanf("%d", &n);
	for (i=1;i<=n;++i)
	{
		scanf("%d %d %d", &xx,&yy1,&yy2);
		x[i]=xx;
		x[i+n]=xx;
		y[i]=yy1;
		y[i+n]=yy2;
	}
	
	okk=0;
	for (i=1;i<=2*n && !okk;++i)
		 for (j=i+1;j<=2*n && !okk;++j)
		 {
			nri=0;//numar de intersectii
			ok=0;
			for (k=1;k<=n && !ok;++k)
				 if (inter(i,j,k)) 
					 nri++;
			     else
					 ok=1;
			if (nri==n) //avem n intersectii
			{
				ind1=i;
				ind2=j;
				okk=1;
			}
		 }
		 
		 
	printf("%d %d %d %d", x[ind1],y[ind1],x[ind2+1],y[ind2+1+n]);

	fclose(stdin);
	fclose(stdout);
	
	return 0;
}