Cod sursa(job #2749526)

Utilizator TeodoraMaria123Serban Teodora Maria TeodoraMaria123 Data 7 mai 2021 00:08:27
Problema Rays Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.24 kb
#include <fstream>
#include <cmath>
#include <algorithm>
using namespace std;
ifstream in("rays.in");
ofstream out("rays.out");
const int nmax=2e5+10;
const int inf=1e9+10;
const double eps=1.0e-14;
struct interval
{
    float inc,fin;
} v[nmax],s[nmax];
bool cmp(interval a,interval b)
{
    if(a.inc==b.inc)
        return a.fin<b.fin;
    return a.inc<b.inc;
}
int main()
{
    int n,i,k,ok,j,ck,c=0;
    float x,y1,y2;
    ///cadranul 1 si 4(x pozitiv)
    in>>n;
    for(i=1; i<=n; i++)
    {
        in>>x>>y1>>y2;
        if(x<0)
            continue;
        if(y1>y2)
            swap(y1,y2);
        v[++c].inc=y1/x;
        v[c].fin=y2/x;
    }
    in.close();
    sort(v+1,v+c+1,cmp);
    s[1].inc=v[1].inc;
    s[1].fin=v[1].fin;
    k=1;
    for(i=2; i<=c; i++)
    {
        ok=0;
        for(j=1; j<=k && !ok; j++)
        {
            if((v[i].inc<=s[j].inc  && s[j].inc<=v[i].fin)||(s[j].inc<=v[i].inc  &&  v[i].inc<=s[j].fin)||(s[j].inc<=v[i].inc  &&  v[i].fin<=s[j].fin))
            {
                ok=1;
                s[j].inc=max(s[j].inc,v[i].inc);
                s[j].fin=min(s[j].fin,v[i].fin);
            }
        }
        if(!ok)
        {
            s[++k].inc=v[i].inc;
            s[k].fin=v[i].fin;
        }
    }
    ck=k;
    ///cadranul 2 si 3 (x negativ)
    ifstream in1("rays.in");
    c=0;
    in1>>n;
    for(i=1; i<=n; i++)
    {
        in1>>x>>y1>>y2;
        if(x>0)
            continue;
        x*=-1;
        if(y1>y2)
            swap(y1,y2);
        v[++c].inc=y1/x;
        v[c].fin=y2/x;
    }
    in1.close();
    sort(v+1,v+c+1,cmp);
    s[1].inc=v[1].inc;
    s[1].fin=v[1].fin;
    k=1;
    for(i=2; i<=c; i++)
    {
        ok=0;
        for(j=1; j<=k && !ok; j++)
        {
            if((v[i].inc<=s[j].inc  && s[j].inc<=v[i].fin)||(s[j].inc<=v[i].inc  &&  v[i].inc<=s[j].fin)||(s[j].inc<=v[i].inc  &&  v[i].fin<=s[j].fin))
            {
                ok=1;
                s[j].inc=max(s[j].inc,v[i].inc);
                s[j].fin=min(s[j].fin,v[i].fin);
            }
        }
        if(!ok)
        {
            s[++k].inc=v[i].inc;
            s[k].fin=v[i].fin;
        }
    }
    k+=ck;
    out<<k;
    return 0;
}