Cod sursa(job #2145260)

Utilizator NicolaalexandraNicola Alexandra Mihaela Nicolaalexandra Data 27 februarie 2018 11:07:22
Problema Rays Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 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 = 1;
    int l = v[1].second;
    for (i=2;i<=n;i++){
        if (v[i].first > l){
            sol++;
            l = v[i].second;
        }
        else
            l = min (l,v[i].second);

        //if (!verif (v[i-1].first,v[i-1].second,v[i].first,v[i].second))
          //  sol++;
    }
    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
    fout<<solve(v,k) + solve (w,k2);

    return 0;
}