Cod sursa(job #1149578)

Utilizator CostanMiriamCostan Miriam CostanMiriam Data 22 martie 2014 01:00:57
Problema Oypara Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.08 kb
#include <fstream>
#include <algorithm>

using namespace std;

ifstream fin ("oypara.in");
ofstream fout ("oypara.out");

struct punct {

    int x;
    int y;
}s[100010],j[100010],pct,S,J;

int arie (punct i, punct j, punct k) {

    double ariec = (j.x-i.x)*(k.y-i.y)-(k.x-i.x)*(j.y-i.y);
    if (ariec<=0.0001)
        return 1;
    else
        return 0;

}

int cmp (punct a, punct b) {

    return arie(pct,a,b);

}
int n,x,y1,y2,i,i1[100010],i2[100010],minimj,minims,iminj,imins,aux1,aux2,p,p1,p2,e,k;

int main () {

    fin>>n;
    for (i=1;i<=n;i++) {
        fin>>x>>y1>>y2;
        j[i].x=s[i].x=x;
        j[i].y=y1;
        s[i].y=y2;
        if (x<minimj) {
            minimj=x;
            iminj=i;
        }else
            if (x==minimj&& y1<j[iminj].y)
                iminj=i;
        if (x<minims) {
            minims=x;
            imins=i;
        }else
            if (x==minims&& y2<s[imins].y)
                imins=i;

    }
    aux1=j[1].x;aux2=j[1].y;
    j[1].x=j[iminj].x;j[1].y=j[iminj].y;
    j[iminj].x=aux1;j[iminj].y=aux2;

    pct=j[1];

    sort (j+2,j+n+1,cmp);

    i1[1]=n;
    i1[2]=n-1;

    p=2;
    for (i=n-2;i>=1;i--) {
        while( arie (j[i1[p-1]],j[i1[p]],j[i]) && p>=1 )
            p--;
        i1[++p]=i;
    }

    i1[++p]=i1[1];

    p1=p;

    aux1=s[1].x;    aux2=s[1].y;
    s[1].x=s[iminj].x;  s[1].y=j[iminj].y;
    s[iminj].x=aux1;    s[iminj].y=aux2;

    pct=s[1];

    sort (s+2,s+n+1,cmp);

    i2[1]=n;
    i2[2]=n-1;

    p=2;
    for (i=n-2;i>=1;i--) {
        while( arie (s[i2[p-1]],s[i2[p]],j[i]) && p>=1 )
            p--;
        i2[++p]=i;
    }
    i2[++p]=i2[1];

    p2=p;


    for (i=1,k=1;i<p2;i++) {
        for (;arie(s[i2[i]], s[i2[i+1]],j[i1[k]])&&k<=p1;k++);

        if (k>=p1) {
            S=s[i2[i]];
            break;
        }
    }
    for (i=1;i<p1;i++)
        if (arie(j[i1[i]],j[i2[i+1]],S)) {
            J=j[i1[i]];
            break;
        }
    fout<<S.x<<" "<<S.y<<" "<<J.x<<" "<<J.y<<"\n";
    return 0;
}