Cod sursa(job #347223)

Utilizator freak93Adrian Budau freak93 Data 11 septembrie 2009 15:14:49
Problema Rays Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.75 kb
#include<fstream>
#include<algorithm>

using namespace std;

const char iname[]="rays.in";
const char oname[]="rays.out";
const int maxn=400005;

ifstream f(iname);
ofstream g(oname);

struct unghi
{
    int x;
    int y;
    bool t;
    int l;
} a[maxn],b[maxn];

bool operator<(const unghi& a,const unghi& b)
{
    return (long long)a.x*(long long)b.y<=(long long)a.y*(long long)b.x;
}

int i,j,n,k,x,y1,y2,t,r,mark[maxn],coada[maxn],poz[maxn],size;

bool fcomp(int x,int y)
{
    return a[x]<a[y];
}

bool fcomp2(int x,int y)
{
    return b[x]<b[y];
}

int main()
{
    f>>n;
    for(i=1;i<=n;++i)
    {
        f>>x>>y1>>y2;
        if(x>0)
            a[++k].x=min(y1,y2),a[k].y=x,a[k].t=true,
            a[++k].x=max(y1,y2),a[k].y=x,a[k].t=false,
            a[k].l=k-1;
        else
            b[++t].x=min(y1,y2),b[t].y=-x,b[t].t=true,
            b[++t].x=max(y1,y2),b[t].y=-x,b[t].t=false,
            b[t].l=t-1;
    }

    for(i=1;i<=k;++i)
        poz[i]=i;
    sort(poz+1,poz+k+1,fcomp);

    for(i=1;i<=k;++i)
        if(a[poz[i]].t==true)
            coada[++size]=poz[i];
        else
            if(mark[a[poz[i]].l]==0)
            {
                for(;size;--size)
                    mark[coada[size]]=1,coada[size]=0;
                ++r;
            }

    for(i=1;i<=t;++i)
        poz[i]=i,mark[i]=0;
    sort(poz+1,poz+t+1,fcomp2);

    for(i=1;i<=t;++i)
        if(b[poz[i]].t==true)
            coada[++size]=poz[i];
        else
            if(mark[b[poz[i]].l]==0)
            {
                for(;size;--size)
                    mark[coada[size]]=1,coada[size]=0;
                ++r;
            }

    g<<r<<"\n";

    f.close();
    g.close();

    return 0;
}