Cod sursa(job #1150083)

Utilizator Impaler_009Mihai Nitu Impaler_009 Data 22 martie 2014 16:09:24
Problema Oypara Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.8 kb
#include <fstream>
#include <iostream>
#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];

struct aprox
{
    int x;
    double y;
}a[100001];

double save;
int n,t;

double mod (double x)
{
    if (x < 0)
        return -x;
    return x;
}

bool cmp2 (aprox a, aprox b)
{
    return mod(a.y-(int)a.y) < mod(b.y-(int)b.y);
}

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

    save = (bot+top)/2;
    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;
    }

    return 0;

    for (int i=1; i<=n; ++i)
    {
        a[i].x = v[i].x;
        a[i].y = mid*v[i].x + save;
    }

    sort (a+1,a+n+1,cmp2);

    fout<<a[1].x<<" "<<(int)a[1].y<<" "<<a[2].x<<" "<<(int)a[2].y;
}