Cod sursa(job #2976143)

Utilizator bem.andreiIceman bem.andrei Data 8 februarie 2023 14:19:37
Problema Oypara Scor 100
Compilator cpp-64 Status done
Runda Lista lui wefgef Marime 1.97 kb
#include <bits/stdc++.h>

using namespace std;
ifstream r("oypara.in");
ofstream w("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()
{
    r>>n;
    for (int i=1; i<=n; i++)
    {
        r>>v[i].x>>v[i].y2>>v[i].y1;
    }
    long double lo = -1000000000;
    long double hi = 1000000000;
    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;
    double 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;
        }
    }
    w<<x1<<" "<<aprox(y1)<<" "<<x2<<" "<<aprox(y2);
}