Cod sursa(job #2543987)

Utilizator betybety bety bety Data 11 februarie 2020 17:59:05
Problema Rays Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream cin("rays.in");
ofstream cout("rays.out");
const int lim=2e5+5;
struct panta
{
    int x,y;
};
struct interval
{
    panta l,r;
}v[lim],w[lim];
bool smaller(panta aa,panta bb)
{
    if(aa.y>=0 and bb.y>=0)
    return aa.x*bb.y>=bb.x*aa.y;
    if(aa.y>=0 and bb.y<0)
    return aa.x*bb.y<=bb.x*aa.y;
    if(aa.y<0 and bb.y>=0)
    return aa.x*bb.y>=bb.x*aa.y;
    if(aa.y<0 and bb.y<0)
    return aa.x*bb.y<=bb.x*aa.y;
}
bool egal(panta aa,panta bb)
{
    return aa.x*bb.y==bb.x*aa.y;
}
int rasp=0;
bool mycmp(interval aa,interval bb)
{
    return smaller(aa.l,bb.l) or
        (egal(aa.l,bb.l) and smaller(aa.r,bb.r));
}
void solve(interval v[],int n)
{
    sort(v+1,v+n+1,mycmp);
    ++rasp;
    panta minn=v[1].l,maxx=v[1].r;
    for(int i=2;i<=n;++i)
    {
        if(smaller(v[i].l,maxx))
        {
            minn=v[i].l;
            if(smaller(v[i].r,maxx))
                maxx=v[i].r;
        }
        else
        {
            ++rasp;
            minn=v[i].l;
            maxx=v[i].r;
        }
    }
}
int main()
{
    int n,x,y1,y2,n1=0,n2=0;
    cin>>n;
    for(int i=1;i<=n;++i)
    {
        cin>>x>>y1>>y2;
        if(x>=0)
            ++n1,v[n1].l.x=v[n1].r.x=x,v[n1].l.y=y2,v[n1].r.y=y1;
        else ++n2,w[n2].l.x=w[n2].r.x=-x,w[n2].l.y=y2,w[n2].r.y=y1;
    }
    solve(v,n1);
    solve(w,n2);
    cout<<rasp;
    return 0;
}