Cod sursa(job #2145294)

Utilizator NicolaalexandraNicola Alexandra Mihaela Nicolaalexandra Data 27 februarie 2018 11:34:43
Problema Rays Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <fstream>
#include <algorithm>
#define DIM 200001
using namespace std;

ifstream fin ("rays.in");
ofstream fout ("rays.out");
pair <int,int> v[DIM],w[DIM];
int n,i,k,k2,X,Y1,Y2;
int cmp (pair<int,int> a, pair<int,int> b){
    if (a.first == b.first)
        return a.second < b.second;
    return a.first < b.first;
}

int solve (pair<int,int> v[],int n){
    sort (v+1,v+n+1,cmp);
    int sol = 0;
    int l = -2000000000;
    for (i=1;i<=n;i++){
        if (v[i].first > l){
            sol++;
            l = v[i].second;
        }
        else
            l = min (l,v[i].second);

    }
    return sol;
}

int main (){

    fin>>n;
    for (i=1;i<=n;i++){
        fin>>X>>Y1>>Y2;
        if (Y1 > Y2)
            swap (Y1,Y2);
        if (X < 0){
            k++;
            v[k].first = Y1;
            v[k].second = Y2;
        }
        else{
            k2++;
            w[k2].first = Y1;
            w[k2].second = Y2;
        }
    }
    /// rezolvam problema pentru cadranul cu x < 0 si pt x > 0
    fout<<solve(v,k) + solve (w,k2);

    return 0;
}