Cod sursa(job #2018575)

Utilizator ionanghelinaIonut Anghelina ionanghelina Data 5 septembrie 2017 14:56:00
Problema Rays Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.67 kb
#include<bits/stdc++.h>
#define maxN 200005

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;

stack<tip> st;

vector<tip> events1,events2;

inline void Solve(vector<tip> events)
{

    while(!st.empty()) st.pop();

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


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

            st.push(*it);

            inStack[it->index]=1;

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

            sol++;

            while(!st.empty())
            {

                int x=st.top().index;
                st.pop();
                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);


    scanf("%d",&n);

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

        scanf("%d%d%d",&x,&y,&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;
}