Cod sursa(job #2207513)

Utilizator Ruxandra985Nanu Ruxandra Laura Ruxandra985 Data 25 mai 2018 20:51:53
Problema Rays Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#include <cstdio>
#include <algorithm>

using namespace std;
struct segm{
    double tan;
    int tip;
    int poz;
};
segm v[400001];
int f[200001],cdr[200001];
int cmp (segm x,segm y){
    if (cdr[x.poz]!=cdr[y.poz])
        return cdr[x.poz]!=cdr[y.poz];
    if (x.tan!=y.tan && cdr[x.poz]==1)
        return x.tan < y.tan;
    else if (x.tan!=y.tan && cdr[x.poz]==2)
        return x.tan > y.tan;
    return x.tip>y.tip;
}
int main()
{
    FILE *fin=fopen ("rays.in","r");
    FILE *fout=fopen ("rays.out","w");
    int n,s,elim,sol,i;
    int x,y1,y2;
    fscanf (fin,"%d",&n);
    s=0;
    for (i=1;i<=n;i++){
        fscanf (fin,"%d%d%d",&x,&y1,&y2);
        if (x<0)
            cdr[i]=2;
        else cdr[i]=1;
        v[++s].tan=(1.0*min(y1,y2))/x;
        v[s].tip=1; // incepe un segment
        v[s].poz=i;
        v[++s].tan=(1.0*max(y1,y2))/x;
        v[s].tip=0; // se termina un segment
        v[s].poz=i;
    }
    // este gresit sa incerc sa normalizez
    sort (v+1,v+s+1,cmp); // am sortat dupa unghiul cu ox
    sol=0;
    elim=0;
    for (i=1;i<=s;i++){

        if (v[i].tip==1) // eveniment 1 : incepe un segment
            f[v[i].poz]=i;
        else {// eveniment 2 : se termina un segment
            if (f[v[i].poz]>elim){ // daca nu l am anulat cu alta ocazie
                sol++;
                elim=i;
            }
        }
    }
    fprintf (fout,"%d",sol);
    return 0;
}