Cod sursa(job #475587)

Utilizator DraStiKDragos Oprica DraStiK Data 7 august 2010 16:23:32
Problema Rays Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.53 kb
#include <algorithm>
#include <vector>
using namespace std;

#define pb push_back
#define mp make_pair
#define DIM 200005
#define sc second
#define fs first

vector <pair <pair <double,int>,int> > vpoz,vneg;
vector <int> st;
int viz[DIM];
int n;

void read ()
{
    int i,x,y1,y2;

    scanf ("%d",&n);
    for (i=1; i<=n; ++i)
    {
        scanf ("%d%d%d",&x,&y1,&y2);
        if (x>0)
        {
            vpoz.pb (mp (mp ((double)min (y1,y2)/x,0),i));
            vpoz.pb (mp (mp ((double)max (y1,y2)/x,1),i));
        }
        else
        {
            vneg.pb (mp (mp ((double)min (y1,y2)/(-x),0),i));
            vneg.pb (mp (mp ((double)max (y1,y2)/(-x),1),i));
        }
    }
}

inline int calc (vector <pair <pair <double,int>,int> > v)
{
    vector <pair <pair <double,int>,int> > :: iterator itv;
    vector <int> :: iterator it;
    int nrc;

    nrc=0;
    st.clear ();
    for (itv=v.begin (); itv!=v.end (); ++itv)
        if (viz[itv->sc]==1)
        {
            ++nrc;
            for (it=st.begin (); it!=st.end (); ++it)
                viz[*it]=2;
            st.clear ();
        }
        else
        {
            st.pb (itv->sc);
            viz[itv->sc]=1;
        }
    return nrc;
}

void solve ()
{
    sort (vpoz.begin (),vpoz.end ());
    sort (vneg.begin (),vneg.end ());
    printf ("%d",calc (vpoz)+calc (vneg));
}

int main ()
{
    freopen ("rays.in","r",stdin);
    freopen ("rays.out","w",stdout);

    read ();
    solve ();

    return 0;
}