Cod sursa(job #1328702)

Utilizator gapdanPopescu George gapdan Data 28 ianuarie 2015 18:06:32
Problema Oypara Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.71 kb
#include<cstdio>
#include<algorithm>
#define NMAX 100005
using namespace std;
struct punct
{
    int x,y;
}p,v1[NMAX],v2[NMAX],st1[NMAX],st2[NMAX];
int n,x,Y1,y2,i,j,k1,k2,poz1,poz2,care,urm,ant;
long long panta(punct a,punct b,punct c)
{
    return 1LL*(b.x-a.x)*1LL*(c.y-a.y)-1LL*(c.x-a.x)*1LL*(b.y-a.y);
}
bool cmp(punct r,punct q)
{
    return panta(p,r,q)<0;
}
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);
        punct X;X.x=x;X.y=Y1;
        v1[i]=X;
        X.y=y2;
        v2[i]=X;
    }
    poz1=1;poz2=1;
    for (i=1;i<=n;++i)
    {
        if (v1[i].y<v1[poz1].y) poz1=i;
            else if (v1[i].y==v1[poz1].y && v1[i].x<v1[poz1].x) poz1=i;
        if (v2[i].y<v2[poz2].y) poz2=i;
            else if (v2[i].y==v2[poz2].y && v2[i].x<v2[poz2].x) poz2=i;
    }
    swap(v1[1],v1[poz1]);
    swap(v2[1],v2[poz2]);
    p=v1[1];
    sort(v1+2,v1+n+1,cmp);
    p=v2[1];
    sort(v2+2,v2+n+1,cmp);
    st1[1]=v1[1];st1[2]=v1[2];k1=2;
    st2[1]=v2[1];st2[2]=v2[2];k2=2;
    for (i=3;i<=n;++i)
    {
        while(k1>=2 && panta(st1[k1-1],st1[k1],v1[i])>=0) --k1;
        st1[++k1]=v1[i];
        while(k2>=2 && panta(st2[k2-1],st2[k2],v2[i])>=0) --k2;
        st2[++k2]=v2[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;
}