Cod sursa(job #1328750)

Utilizator gapdanPopescu George gapdan Data 28 ianuarie 2015 18:43:55
Problema Oypara Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.35 kb
#include<cstdio>
#include<algorithm>
#include<vector>
#define NMAX 100005
using namespace std;
struct punct
{
    int x,y;
}p,v1[NMAX],v2[NMAX],st1[NMAX],st2[NMAX];
struct lpunct
{
    int x,Y1,y2;
};
vector<lpunct>mul;
 bool  cmp (lpunct l1, lpunct l2)
{
	return l1.x < l2.x;
}
int viz1[NMAX],viz2[NMAX],sol1[NMAX],sol2[NMAX];
int n,x,Y1,y2,i,j,k1,k2,poz1,poz2,care,urm,ant;
long long panta(punct p3,punct p1,punct p2)
{
	long long line[3];
	line[0]=p1.y-p2.y;
	line[1]=p2.x-p1.x;
	line[2]=-p1.x*line[0]-p1.y*line[1];
	return p3.x*line[0]+p3.y*line[1]+line[2];
}
int main()
{
    freopen("oypara.in","r",stdin);
    freopen("oypara.out","w",stdout);
    scanf("%d",&n);
    for (i=1;i<=n;++i)
    {
        scanf("%d%d%d",&x,&Y1,&y2);
        lpunct X;X.x=x;X.Y1=Y1;X.y2=y2;
        mul.push_back(X);
    }
    sort(mul.begin(),mul.end(),cmp);
    for (i=0;i<n;++i)
    {
        lpunct Y;
        Y=mul[i];
        v1[i+1].x=Y.x;v1[i+1].y=Y.Y1;
        v2[i+1].x=Y.x;v2[i+1].y=Y.y2;
    }
    st1[1]=v1[1];sol1[1]=1;k1=1;
    st2[1]=v2[1];sol2[1]=1;k2=1;
    for (i=2;i<=n;++i)
    {
        while(k1>=2 && panta(v1[i],st1[k1],st1[k1-1])<0)
        {
            viz1[sol1[k1]]=0;
            --k1;
        }
        st1[++k1]=v1[i];
        sol1[k1]=i;
        while(k2>=2 && panta(v2[i],st2[k2],st2[k2-1])<0)
        {
            viz2[sol2[k2]]=0;
            --k2;
        }
        st2[++k2]=v2[i];
        sol2[k2]=i;
    }
    for (i=n;i>0;--i)
    {
        if (viz1[i]==0)
        {
            while(k1>=2 && panta(v1[i],st1[k1],st1[k1-1])<0)
            {
                viz1[sol1[k1]]=0;
                --k1;
            }
            st1[++k1]=v1[i];
            sol1[k1]=i;
        }
        if (viz2[i]==0)
        {
            while(k2>=2 && panta(v2[i],st2[k2],st2[k2-1])<0)
            {
                viz2[sol2[k2]]=0;
                --k2;
            }
            st2[++k2]=v2[i];
            sol2[k2]=i;
        }
    }

    care=0;
    for (i=1;i<=k1;++i)
    {
        while (true)
        {
            if (care==k2) urm=0;
                else urm=care+1;
            if (panta(st2[urm],st1[i],st2[care])>=0) break;
            care=urm;
        }
        while(true)
        {
            if (care==0) ant=k2-1;
                else ant=care-1;
            if (panta(st2[ant],st1[i],st2[care])>=0) break;
            care=ant;
        }
        if (i==k1) urm=0;
            else urm=i+1;
        if (i==1) ant=k1;
            else ant=i-1;
        if (panta(st1[urm],st1[i],st2[care])<=0 && panta(st1[ant],st1[i],st2[care])<=0)
        {
            printf("%d %d %d %d\n",st1[i].x,st1[i].y,st2[care].x,st2[care].y);
			return 0;
        }
    }
    care=0;
	for(i=1;i<=k1;++i)
	{
		while(true)
		{
			if (care==k2) urm=0;
                else urm=care+1;
			if(panta(st2[urm],st1[i],st2[care])<0) break;
			care=urm;
		}
		// incercam precendetul
		while(true)
		{
			if (care==0) ant=k2;
                else ant=care-1;
			if(panta(st2[ant],st1[i],st2[care])<0)break;
			care=ant;
		}
		if (i==k1) urm=0;
            else urm=i+1;
		if (i==0) ant=k1;
            else ant=i-1;

		if(panta(st1[urm],st1[i],st2[care])>0 && panta(st1[ant],st1[i],st2[care])>0)
		{
			printf("%d %d %d %d\n",st1[i].x,st1[i].y,st2[care].x,st2[care].y);
			return 0;
		}
	}

    return 0;
}