Cod sursa(job #2075176)

Utilizator bogdi1bogdan bancuta bogdi1 Data 25 noiembrie 2017 11:43:25
Problema Rays Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.99 kb
#include <cstdio>
#include <algorithm>
#include<cmath>
const double eps = 1.e-14;
using namespace std;
struct Segmente
{
    double x,y;
} stanga[200005];
struct Segmente2
{
    double x,y;
} dreapta[200005];
bool cmp(Segmente a, Segmente b)
{
    if(fabs(a.x-b.x)<eps)
        return a.y<b.y;
    return a.x<b.x;
}
bool cmp1(Segmente2 a, Segmente2 b)
{
    if(fabs(a.x-b.x)<eps)
        return a.y<b.y;
    return a.x<b.x;
}
int main()
{   freopen("rays.in", "r",stdin);
    freopen("rays.out", "w",stdout);
    int n,k,kk,i,x,y1,y2,nr;
    double dr,st;
    scanf("%d", &n);
    k=0;
    kk=0;
    for(i=1; i<=n; i++){
        scanf("%d%d%d", &x, &y1, &y2);
        if(x<0){
            x*=-1;
            if(y1<=y2){
                stanga[++k].x=(double)y1/x;
                stanga[k].y=(double)y2/x;
            }
            else{
                stanga[++k].x=(double)y2/x;
                stanga[k].y=(double)y1/x;
            }
        }
        else{
            if(y1<=y2){
                dreapta[++kk].x=(double)y1/x;
                dreapta[kk].y=(double)y2/x;
            }
            else{
                dreapta[++kk].x=(double)y2/x;
                dreapta[kk].y=(double)y1/x;
            }
        }
    }
    sort(stanga+1, stanga+k+1,cmp);
    sort(dreapta+1, dreapta+kk+1,cmp1);
    if(k>0)
        nr=1;
    st=stanga[1].x;
    dr=stanga[1].y;
    for(i=2; i<=k; i++){
        if(stanga[i].x<=dr){
            st=stanga[i].x;
            dr=min(dr, stanga[i].y);
        }
        else{
            nr++;
            st=stanga[i].x;
            dr=stanga[i].y;
        }
    }
    if(kk>0)
        nr++;
    st=dreapta[1].x;
    dr=dreapta[1].y;
    for(i=2; i<=kk; i++){
        if(dreapta[i].x<=dr){
            st=dreapta[i].x;
            dr=min(dr, dreapta[i].y);
        }
        else{
            nr++;
            st=dreapta[i].x;
            dr=dreapta[i].y;
        }
    }
    printf("%d", nr);
    return 0;
}