Cod sursa(job #1127356)

Utilizator chiriacandrei25Chiriac Andrei chiriacandrei25 Data 27 februarie 2014 12:07:46
Problema Rays Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.69 kb
#include <cstdio>
#include <algorithm>
#define Nmax 200005
#define eps 0.0000001

using namespace std;

struct segm
{
    double p1,p2;
};
segm a[Nmax],b[Nmax];
int sol,len1,len2;

inline bool Cmp(const segm A, const segm B)
{
    if(A.p1==B.p1)
        return A.p2<B.p2;
    return A.p1<B.p1;
}

inline void Greedy(const segm a[], const int N)
{
    int i;
    double minim,maxim,st,dr;
    ++sol;
    minim=min(a[1].p1,a[1].p2);
    maxim=max(a[1].p1,a[1].p2);
    for(i=2;i<=N;++i)
    {
        st=min(a[i].p1,a[i].p2);
        dr=max(a[i].p1,a[i].p2);
        if((dr>=minim && st<=maxim))
        {
            minim=max(minim,st);
            maxim=min(maxim,dr);
        }
        else
        {
            ++sol;
            minim=st; maxim=dr;
        }
    }
}

int main()
{
    int i,N,x,y1,y2;
    double aux;
    freopen ("rays.in","r",stdin);
    freopen ("rays.out","w",stdout);
    scanf("%d", &N);
    for(i=1;i<=N;++i)
    {
        scanf("%d%d%d", &x,&y1,&y2);
        if(x>0)
        {
            ++len1;
            a[len1].p1=(double)y1/x;
            a[len1].p2=(double)y2/x;
            if(a[len1].p1>a[len1].p2)
            {
                aux=a[len1].p1; a[len1].p1=a[len1].p2; a[len1].p2=aux;
            }
        }
        else
        {
            ++len2;
            b[len2].p1=(double)y1/x;
            b[len2].p2=(double)y2/x;
            if(b[len2].p1>b[len2].p2)
            {
                aux=b[len2].p1; b[len2].p1=b[len2].p2; b[len2].p2=aux;
            }
        }
    }
    sort(a+1,a+len1+1,Cmp);
    sort(b+1,b+len2+1,Cmp);
    Greedy(a,len1); Greedy(b,len2);
    printf("%d\n", sol);
    return 0;
}