Cod sursa(job #2207537)

Utilizator Ruxandra985Nanu Ruxandra Laura Ruxandra985 Data 25 mai 2018 21:52:18
Problema Rays Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <cstdio>
#include <algorithm>

using namespace std;
pair <double,double> st[400001],dr[400001];

int main()
{
    FILE *fin=fopen ("rays.in","r");
    FILE *fout=fopen ("rays.out","w");
    int n,sol,i,ss,sd;
    int x,y1,y2;
    double sfmin;
    fscanf (fin,"%d",&n);
    ss=sd=0;
    for (i=1;i<=n;i++){
        fscanf (fin,"%d%d%d",&x,&y1,&y2);
        if (y1>y2)
            swap(y1,y2);
        if (x<0){
            st[++ss].first=-(1.0*y1)/x;
            st[ss].second=-(1.0*y2)/x;
        }
        else{
            dr[++sd].first=(1.0*y1)/x;
            dr[sd].second=(1.0*y2)/x;
        }
    }
    // este gresit sa incerc sa normalizez
    sort (st+1,st+ss+1); // am sortat dupa unghiul cu ox
    sort (dr+1,dr+sd+1);
    sol=2;
    sfmin=1.0*2000000000;
    for (i=1;i<=ss;i++){
        if (st[i].first<=sfmin) // eveniment 1 : incepe un segment
            sfmin=min(sfmin,st[i].second);
        else {// eveniment 2 : se termina un segment
            sol++;
            sfmin=1.0*2000000000;
        }
    }
    sfmin=1.0*2000000000;
    for (i=1;i<=sd;i++){
        if (dr[i].first<=sfmin) // eveniment 1 : incepe un segment
            sfmin=min(sfmin,dr[i].second);
        else {// eveniment 2 : se termina un segment
            sol++;
            sfmin=1.0*2000000000;
        }
    }
    fprintf (fout,"%d",sol);
    return 0;
}