Cod sursa(job #1339626)

Utilizator danyro364Savu Ioan Daniel danyro364 Data 11 februarie 2015 00:25:04
Problema Rays Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.46 kb
//#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#define nmax 400001
using namespace std;
FILE *f=fopen("rays.in","r"),*g=fopen("rays.out","w");
struct punct{
    int x,y;
    int tip,id;/*tip 0=inceput, tip 1=sfarsit*/
}poz[nmax],neg[nmax];
int lgpoz,lgneg,nr,viz[nmax/2+1];
int criteriu(punct a, punct b)
{
    double ua,ub;
    //cout<<a.x<<" "<<a.y<<"-"<<b.x<<" "<<b.y<<"\n";
    ua=(double)a.y/a.x; ub=(double)b.y/b.x;
    //cout<<ua<<" "<<ub<<"\n";
    if(ua<ub)
        return 1;
    return 0;
}
int main()
{
    int i,j,n,x,maxid=0; queue <punct> q; punct aux;
    fscanf(f,"%d",&n);
    for(i=1;i<=n;i++)
    {
        fscanf(f,"%d",&x);
        if(x<0)
        {
            x=-x;
            fscanf(f,"%d %d",&neg[++lgneg].y,&neg[++lgneg].y);
            neg[lgneg-1].x=x; neg[lgneg].x=x;
            neg[lgneg-1].id=neg[lgneg].id=i;
            if(neg[lgneg-1].y<neg[lgneg].y)
            {
                neg[lgneg-1].tip=0;
                neg[lgneg].tip=1;
            }
            else
            {
                neg[lgneg-1].tip=1;
                neg[lgneg].tip=0;
            }
        }
        else
        {
            fscanf(f,"%d %d",&poz[++lgpoz].y,&poz[++lgpoz].y);
            poz[lgpoz-1].x=poz[lgpoz].x=x;
            poz[lgpoz-1].id=poz[lgpoz].id=i;
            if(poz[lgpoz-1].y<poz[lgpoz].y)
            {
                poz[lgpoz-1].tip=0;
                poz[lgpoz].tip=1;
            }
            else
            {
                poz[lgpoz-1].tip=1;
                poz[lgpoz].tip=0;
            }
        }
    }
    sort(neg+1,neg+lgneg+1,criteriu);
    sort(poz+1,poz+lgpoz+1,criteriu);
    for(i=1;i<=lgneg;i++)
    if(!viz[neg[i].id])
    {

        q.push(neg[i]);
        if(neg[i].tip==1)
        {
            nr++;
            while(!q.empty())
            {
                aux=q.front();
                q.pop();
                viz[aux.id]=1;
                if(aux.id>maxid) maxid=aux.id;
            }
        }
    }
    for(i=1;i<=maxid;i++)
        viz[i]=0;
    for(i=1;i<=lgpoz;i++)
    if(!viz[poz[i].id])
    {
        q.push(poz[i]);
        if(poz[i].tip==1)
        {
            nr++;
            while(!q.empty())
            {
                aux=q.front();
                q.pop();
                viz[aux.id]=1;
            }
        }
    }
    fprintf(g,"%d",nr);
    fclose(f);
    fclose(g);
    return 0;
}