Cod sursa(job #3188923)

Utilizator biancalautaruBianca Lautaru biancalautaru Data 4 ianuarie 2024 00:57:52
Problema Rays Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.41 kb
#include <fstream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <bitset>
#include <stack>
#define DIM 200001
using namespace std;
ifstream fin("rays.in");
ofstream fout("rays.out");
int n,x,y1,y2;
vector<pair<pair<int,int>,int>> st,dr;
stack<int> s;
bitset<DIM> f;

bool cmp(pair<pair<int,int>,int> a,pair<pair<int,int>,int> b) {
    long long aux=1LL*a.first.first*b.first.second-1LL*a.first.second*b.first.first;
    if (aux==0)
        return a.second<b.second;
    return aux<0;
}

int calc(vector<pair<pair<int,int>,int>> v) {
    int cnt=0;
    sort(v.begin(),v.end(),cmp);
    while (!s.empty())
        s.pop();
    f.reset();
    for (int i=0;i<v.size();i++) {
        int tip=v[i].second;
        if (tip>0)
            s.push(i);
        else
            if (f[-tip]==0) {
                cnt++;
                while (!s.empty()) {
                    f[v[s.top()].second]=1;
                    s.pop();
                }
            }
    }
    return cnt;
}

int main() {
    fin>>n;
    for (int i=1;i<=n;i++) {
        fin>>x>>y1>>y2;
        if (y1>y2)
            swap(y1,y2);
        if (x>0) {
            st.push_back({{y1,x},i});
            st.push_back({{y2,x},-i});
        }
        else {
            dr.push_back({{y1,-x},i});
            dr.push_back({{y2,-x},-i});
        }
    }
    fout<<calc(st)+calc(dr);
    return 0;
}