Cod sursa(job #1782877)

Utilizator felixiPuscasu Felix felixi Data 18 octombrie 2016 16:50:34
Problema Oypara Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.82 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 = -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;
        }
    }
 
    fout<<x1<<" "<<aprox(y1)<<" "<<x2<<" "<<aprox(y2);
}