Cod sursa(job #1150043)

Utilizator Impaler_009Mihai Nitu Impaler_009 Data 22 martie 2014 15:26:57
Problema Oypara Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.61 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];
double save;
int n,t;

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

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

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

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

        if (newtop < top)
        {
            top = newtop;
            if (top < bot)
                return -1;
        }

        if (newbot > bot)
        {
            bot = newbot;
            if (top < bot)
                return 1;
        }
    }

    return 0;
}

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);

    double lo = -100000000;
    double hi = 100000000;
    double mid;

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

        int ok = check (mid);

        if (!ok)
         break;

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

    for (int i=1; i<=n; ++i)
    {
        double 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;
}