Cod sursa(job #2082428)

Utilizator livliviLivia Magureanu livlivi Data 6 decembrie 2017 10:18:24
Problema Oypara Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.33 kb
#include<fstream>
#include<algorithm>
#include<vector>
#define M 100000000
#define N 10000000
#define K 1000
#define EPS 1e-8
using namespace std;

class mazi{     ///segment
public:
    int x,y1,y2;

    mazi(int _x=0,int _y1=0,int _y2=0){
        x=_x;
        y1=_y1;
        y2=_y2;
    }

    bool operator <(const mazi a) const{
        if (x<a.x) return true;
        if (x==a.x &&y1<a.y1) return true;
        if (x==a.x &&y1==a.y1 &&y2<a.y2) return true;
        return false;
    }
};

vector<mazi> v;

ifstream cin("oypara.in");
ofstream cout("oypara.out");

int verif(double start,int x){
    double st=-10*M,dr=+10*M;

    for(int i=1;i<v.size();i++){
        double a=(1.0*v[i].y1-start)/(1.0*v[i].x-x);
        double b=(1.0*v[i].y2-start)/(1.0*v[i].x-x);

        if (a>dr) return -1;
        if (b<st) return 1;

        if (a>st) st=a;
        if (b<dr) dr=b;
    }

    return 0;
}

double panta(double start,int x){
    double st=-10*M,dr=+10*M;

    for(int i=1;i<v.size();i++){
        double a=(1.0*v[i].y1-start)/(1.0*v[i].x-x);
        double b=(1.0*v[i].y2-start)/(1.0*v[i].x-x);

        if (a>st) st=a;
        if (b<dr) dr=b;
    }

    if ((int)st!=(int)dr) return ((int)st+(int)dr+1)/2;
    return (st+dr)/2;
}

int main(){
    int n,i;

    cin>>n;
    for(i=1;i<=n;i++){
        int a,b,c;
        cin>>a>>b>>c;
        v.push_back(mazi(a,b,c));
    }

    sort(v.begin(),v.end());

    double st=v[0].y1,dr=v[0].y2;
    double start=(st+dr)/2;
    for(i=1;i<=K;i++){
        int aux=verif(start,v[0].x);

        if (verif((int)start,v[0].x)==0){
            start=(int)start;
            break;
        }

        if (aux<0) dr=start;
        else st=start;

        start=(st+dr)/2;
    }

    double a=panta(start,v[0].x);
    double b=start-a*v[0].x;

    int a1;
    int b1=0;
    for(a1=1;a1<=N;a1++){
        double aux=a*a1+b;
        if (aux-(int)aux<EPS &&(int)aux>=1 &&(int)aux<=M){
            b1=(int)aux;
            break;
        }
        if ((int)aux+1-aux<EPS &&(int)aux>=0 &&(int)aux<M){
            b1=(int)aux+1;
            break;
        }
    }

    if (b1==0){
        for(a1=10*M;a1>=10*M-N;a1--){
            double aux=a*a1+b;
            if (aux-(int)aux<EPS &&(int)aux>=1 &&(int)aux<=M){
                b1=(int)aux;
                break;
            }
            if ((int)aux+1-aux<EPS &&(int)aux>=0 &&(int)aux<M){
                b1=(int)aux+1;
                break;
            }
        }
    }

    cout<<a1<<' '<<b1<<' ';

    b1=0;
    for(a1++;a1<=N;a1++){
        double aux=a*a1+b;
        if (aux-(int)aux<EPS &&(int)aux>=1 &&(int)aux<=M){
            b1=(int)aux;
            break;
        }
        if ((int)aux+1-aux<EPS &&(int)aux>=0 &&(int)aux<M){
            b1=(int)aux+1;
            break;
        }
    }

    if (b1==0){
        if (a1<=10*M-N) a1=10*M;
        else a1--;

        for(;a1>=10*M-N;a1--){
            double aux=a*a1+b;
            if (aux-(int)aux<EPS &&(int)aux>=1 &&(int)aux<=M){
                b1=(int)aux;
                break;
            }
            if ((int)aux+1-aux<EPS &&(int)aux>=0 &&(int)aux<M){
                b1=(int)aux+1;
                break;
            }
        }
    }

    cout<<a1<<' '<<b1<<endl;
    return 0;
}