Cod sursa(job #2145359)

Utilizator NicolaalexandraNicola Alexandra Mihaela Nicolaalexandra Data 27 februarie 2018 12:14:33
Problema Rays Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <fstream>
#include <algorithm>
#include <cmath>
#define DIM 200001
using namespace std;

ifstream fin ("rays.in");
ofstream fout ("rays.out");
pair <double,double> 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<double,double> v[],int n){
    if (n == 0)
        return 0;
    sort (v+1,v+n+1);
    int sol = 0;
    double l = (1<<31);
   // l *= -1;
    for (int 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/abs(1.0*X);
            v[k].second = Y2/abs(1.0*X);
        }
        else{
            k2++;
            w[k2].first = Y1/(1.0*X);
            w[k2].second = Y2/(1.0*X);
        }
    }
    /// rezolvam problema pentru cadranul cu x < 0 si pt x > 0
    fout<<solve(v,k) + solve (w,k2);

    return 0;
}