Cod sursa(job #2018579)

Utilizator ionanghelinaIonut Anghelina ionanghelina Data 5 septembrie 2017 14:59:09
Problema Rays Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.21 kb
#include<bits/stdc++.h>
#define maxN 200005
#define dim 1000000
using namespace std;

typedef struct tip
{
    double slope;
    int index,type;
};

bool cmp(tip a,tip b)
{
    if(a.slope==b.slope) return a.index<b.index;
    return a.slope<b.slope;
}

bool inStack[maxN];

int sol,vf;

tip st[maxN];


char buff[dim+5];
int pos=0;

vector<tip> events1,events2;


inline void read(int &nr)
{
    nr=0;
    while(buff[pos]<'0' || buff[pos]>'9')
    {
        pos++;
        if(pos==dim)
        {
            pos=0;
            fread(buff,1,dim,stdin);
        }
    }
    while(buff[pos]>='0' && buff[pos]<='9')
    {
        nr=nr*10+buff[pos]-'0';
        pos++;
        if(pos==dim)
        {
            pos=0;
            fread(buff,1,dim,stdin);
        }
    }
}
inline void Solve(vector<tip> events)
{

    vf=0;

    memset(inStack,0,sizeof(inStack));


    for(vector<tip>::iterator it=events.begin();it!=events.end();it++)
    {
        if(it->type==0)
        {

            //st.push(*it);
            st[++vf]=*it;

            inStack[it->index]=1;

        }
            else
        {
            if(!inStack[it->index]) continue;

            sol++;

            while(vf)
            {

                int x=st[vf].index;
                vf--;
                inStack[x]=0;
              //  if(x==it->index) break;

            }

        }

    }
}
int n,x,y,z;
int main()
{
    freopen("rays.in","r",stdin);
    freopen("rays.out","w",stdout);


    fread(buff,1,dim,stdin);
    read(n);

    for(int i=1;i<=n;i++)
    {

     //   scanf("%d%d%d",&x,&y,&z);
        read(x);
        read(y);
        read(z);
        if(y>z) swap(y,z);

        if(x>0)
        {

            events1.push_back({(1.0*y)/x,i,0});

            events1.push_back({(1.0*z)/x,i,1});

        }

            else

        {

            events2.push_back({(-1.0*y)/x,i,0});

            events2.push_back({(-1.0*z)/x,i,1});
        }

    }

    sort(events1.begin(),events1.end(),cmp);

    sort(events2.begin(),events2.end(),cmp);

    Solve(events1);

    Solve(events2);

    printf("%d\n",sol);

    return 0;
}