Cod sursa(job #1150412)

Utilizator Impaler_009Mihai Nitu Impaler_009 Data 22 martie 2014 23:05:54
Problema Oypara Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.77 kb
#include <fstream>
using namespace std;

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

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

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

int aprox (double x)
{
    if (x - (int)x < (int)x+1 - x)
    return (int)x;
    return (int)x+1;
}

int check (long double m)
{
    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 (newbot > bot)
        {
            bot = newbot;
            if (top < bot)
                return 1;
        }

        if (newtop < top)
        {
            top = newtop;
            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].y2>>v[i].y1;

    long double lo = -1000000;
    long double hi = 1000000;
    long double mid;

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

        int ok = check (mid);

        if (!ok)
         break;

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

    int x1=v[1].x, x2=v[2].x ,y1 = mid*v[1].x + save, y2 = mid*v[2].x + save;

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

        if (mod(y-aprox(y)) < mod(y1-aprox(y1)))
        {
            y2 = y1;
            x2 = x1;
            y1 = y;
            x1 = v[i].x;
        }
        else if (mod(y-aprox(y)) < mod(y2-aprox(y2)))
        {
            y2 = y;
            x2 = v[i].x;
        }
    }

    fout<<x1<<" "<<y1<<" "<<x2<<" "<<y2;
}