Cod sursa(job #2017355)

Utilizator LeVladzCiuperceanu Vlad LeVladz Data 31 august 2017 22:23:14
Problema Rays Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.55 kb
#include <cstdio>
#include <algorithm>
#include <bitset>
#include <vector>
#include <stack>
#define X first.first
#define Y first.second
#define Z second
#define DIM 200001
#define DIMBUFF 100001

using namespace std;

FILE *fin = fopen("rays.in", "r");
FILE *fout = fopen("rays.out", "w");

int n,x1,x2,y1,sol,i;
vector < pair < pair <int, int>, int > > sus, jos;
stack <int> st;
bitset <DIM> v;

int cmp(pair < pair <int, int>, int > a, pair < pair <int, int>, int >  b)
{
    long long t = a.X*b.Y-a.Y*b.X;
    if (t == 0)
        return a.Z < b.Z;
    else
        return t < 0;
}

char buff[DIMBUFF];
int pp;

int numar()
{
    int val = 0, semn;
    while (!(buff[pp] >= '0' && buff[pp] <= '9') && buff[pp] != '-')
    {
        pp++;
        if (pp == DIMBUFF)
        {
            fread(buff, 1, DIMBUFF, fin);
            pp = 0;
        }
    }
    if (buff[pp] == '-')
    {
        semn = -1;
        pp++;
        if (pp == DIMBUFF)
        {
            fread(buff, 1, DIMBUFF, fin);
            pp = 0;
        }
    }
    else
        semn = 1;
    while (buff[pp] >= '0' && buff[pp] <= '9')
    {
        val = val*10+buff[pp]-'0';
        pp++;
        if (pp == DIMBUFF)
        {
            fread(buff, 1, DIMBUFF, fin);
            pp = 0;
        }
    }
    return val * semn;
}

int main ()
{
    n = numar();
    for (i=1; i<=n; i++)
    {
        y1 = numar();
        x1 = numar();
        x2 = numar();
        if (x1 > x2)
            swap(x1, x2);
        if (y1 > 0)
        {
            sus.push_back(make_pair(make_pair(x1, y1),i));
            sus.push_back(make_pair(make_pair(x2, y1),-i));
        }
        else
        {
            jos.push_back(make_pair(make_pair(x1, -y1),i));
            jos.push_back(make_pair(make_pair(x2, -y1),-i));
        }
    }
    int T = 2;
    for (;T--;)
    {
        sort(sus.begin(), sus.end(), cmp);
        while (!st.empty())
            st.pop();
        v.reset();
        for (int i=0;i<sus.size(); i++)
        {
            if (sus[i].Z > 0)
                st.push(i);
            else
                if (v[-sus[i].Z] == 0)
                {
                    sol++;
                    while (!st.empty())
                    {
                        v[sus[st.top()].Z] = 1;
                        st.pop();
                    }
                }
        }
        sus.clear();
        for (i=0; i<jos.size(); i++)
            sus.push_back(jos[i]);
    }
    fprintf(fout, "%d", sol);
    return 0;
}