Cod sursa(job #2015538)

Utilizator mariusn01Marius Nicoli mariusn01 Data 26 august 2017 16:14:28
Problema Rays Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.78 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <stack>
#include <bitset>
#include <algorithm>
#define DIM 200010
#define X first.first
#define Y first.second
#define Z second

using namespace std;

vector<pair<pair<long long, long long>, long long > >S, J;
long long n, x1, x2, y, sol;
stack<long long> st;
bitset<DIM> B;

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

int main () {
    ifstream fin ("rays.in");
    ofstream fout("rays.out");

    fin>>n;
    for (long long i=1;i<=n;i++) {
        fin>>y>>x1>>x2;
        if (x1 > x2) {
            swap(x1, x2);
        }
        if (y > 0) {
            S.push_back(make_pair(make_pair(x1, y),i));
            S.push_back(make_pair(make_pair(x2, y),-i));
        }else {
            J.push_back(make_pair(make_pair(x1, -y),i));
            J.push_back(make_pair(make_pair(x2, -y),-i));
        }
    }


    for (long long t = 2; t--;) {



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

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

        for (long long i=0;i<S.size(); i++) {
            long long tip = S[i].Z;
            if (tip > 0) {
                st.push(i);
            } else {
                if (B[-tip] == 0) {
                    sol ++;
                    while (!st.empty()) {
                        B[ S[st.top()].Z ] = 1;
                        st.pop();
                    }
                }
            }
        }

        S.clear();
        for (long long i=0;i<J.size();i++)
            S.push_back(J[i]);
    }
    fout<<sol;
    return 0;
}