Cod sursa(job #1745438)

Utilizator popabogdanPopa Bogdan Ioan popabogdan Data 21 august 2016 21:19:17
Problema Rays Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.01 kb
#include <bits/stdc++.h>
#define nmax 200001
using namespace std;
ifstream fin("rays.in");
ofstream fout("rays.out");
struct ev
{
    int x,y1,y2,cp;//1 in, -1 out, 0 neutru
    double t;
};
ev st[2*nmax],dr[2*nmax];
int n,lgs,lgd,i,x,y,y2,glont,f;
queue<ev>e;
double t;
int qx(ev a, ev b)
{
    return a.t>b.t;
}
int cauts(ev a)
{
    int s=1,d=lgs,m,best;
    double t=(double)a.y2/a.x;
    while(s<=d)
    {
        m=(s+d)/2;
        if(st[m].t<=t)best=m,d=m-1;
        else s=m+1;
    }
    return best;
}
int cautd(ev a)
{
    int s=1,d=lgd,m,best;
    double t=(double)a.y2/a.x;
    while(s<=d)
    {
        m=(s+d)/2;
        if(dr[m].t>=t)best=m,d=m-1;
        else s=m+1;
    }
    return best;
}
int main()
{
    fin>>n;
    for(i=1;i<=n;i++)
    {
        fin>>x>>y>>y2;
        if(y>y2)swap(y,y2);
        if(x<0)
        {
            st[++lgs]={x,y,y2,1,(double)y/x};
            st[++lgs]={x,y2,y,-1,(double)y2/x};
        }
        else
        {
             dr[++lgd]={x,y,y2,1,(double)y/x};
             dr[++lgd]={x,y2,y,-1,(double)y2/x};
        }
    }
    sort(st+1,st+lgs+1,qx);
    sort(dr+1,dr+lgd+1,qx);
    reverse(dr+1,dr+lgd+1);
    for(i=1;i<=lgs;i++)
        if(st[i].cp==1)
            e.push(st[i]);
        else
        if(st[i].cp==-1)
        {
            glont++;
            while(!e.empty())
            {
                f=cauts(e.front());
                while(!(st[f].x==e.front().x && st[f].y1==e.front().y2))f++;
                st[f].cp=0;
                e.pop();
            }
        }
    for(i=1;i<=lgd;i++)
        if(dr[i].cp==1)
            e.push(dr[i]);
        else
            if(dr[i].cp==-1)
        {
            glont++;
            while(!e.empty())
            {
                f=cautd(e.front());
                while(!(dr[f].x==e.front().x && dr[f].y1==e.front().y2))f++;
                dr[f].cp=0;
                e.pop();
            }
        }
    fout<<glont<<"\n";
    return 0;
}