Cod sursa(job #1148860)

Utilizator Impaler_009Mihai Nitu Impaler_009 Data 21 martie 2014 10:44:36
Problema Oypara Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.53 kb
#include <fstream>
#include <algorithm>

#define ll long long

using namespace std;

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

struct segm
{
    int x,y1,y2;
}v[100001],sol[3];
ll save;
int n,t;

bool cmp (segm a, segm b)
{
    return a.x < b.x;
}

int check (ll m)
{
    //y-y0 = m(x-x0)

    ll top = -m*v[1].x + v[1].y1;
    ll bot = -m*v[1].x + v[1].y2;

    ll inittop = top, initbot = bot;

    for (int i=2; i<=n; ++i)
    {
        ll newtop = -m*v[i].x + v[i].y1;
        ll newbot = -m*v[i].x + v[i].y2;

        top = min (top,newtop);
        bot = max (bot,newbot);
    }

    if (bot <= top)
    {
        save = bot;
        return 0;
    }

    if ( top < initbot )
      return -1;
    return 1;
}

int main()
{
    fin>>n;

    for (int i=1; i<=n; ++i)
      {
          fin>>v[i].x>>v[i].y1>>v[i].y2;
          if (v[i].y1 < v[i].y2)
           swap (v[i].y1, v[i].y2);
      }

    sort (v+1,v+n+1,cmp);

    ll lo = -10000;
    ll hi = 10000;
    ll mid;

    while (1)
    {
        mid  = (lo + hi)/2;

        int ok = check (mid);

        if (!ok)
         break;

        if (ok==1)
          lo = mid+1;
        else hi = mid-1;
    }

    for (int i=1; i<=n; ++i)
    {
        ll y = mid*v[i].x + save;
        if (y > 0)
        {
            sol[++t].x = v[i].x;
            sol[t].y1 = y;

            if (t == 2)
            break;
        }
    }

    fout<<sol[1].x<<" "<<sol[1].y1<<" "<<sol[2].x<<" "<<sol[2].y1;
}