Cod sursa(job #573983)

Utilizator TeodoraTanaseTeodora Tanase TeodoraTanase Data 6 aprilie 2011 18:50:27
Problema Rays Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.67 kb
#include <cstdio>
#include <algorithm>

using namespace std;

const int M=200005;
int n, x, n1, n2, f, y1, y2;

struct panta
{
    double m1, m2;
} pd[M], ps[M];

struct frigi
{
    double x, y;
} a[M];

void citire()
{
    scanf ("%d ",&n);
    for (int z=1; z<=n; ++z)
    {
        scanf ("%d %d %d ",&x,&y1,&y2);
        if (x>0)
        {
            pd[n1].m1=(double)y1/x;
            pd[n1].m2=(double)y2/x;
            if (pd[n1].m1>pd[n1].m2)
            {
                double aux=pd[n1].m1;
                pd[n1].m1=pd[n1].m2;
                pd[n1].m2=aux;
            }
            n1++;
        }
        else
        {
            ps[n2].m1=(double)y1/(-x);
            ps[n2].m2=(double)y2/(-x);
            if (ps[n2].m1>ps[n2].m2)
            {
                double aux=ps[n2].m1;
                ps[n2].m2=ps[n2].m1;
                ps[n2].m1=aux;
            }
            n2++;
        }
    }
}

bool cmp(panta a,panta b)
{
    if (a.m2>b.m2)
        return false;
    if (a.m2==b.m2 && a.m1>b.m1)
        return false;
    return true;
}

void frigidere(panta pd[], int n1)
{
    for (int i=0; i<n1; i++)
    {
        f++;
        double m=pd[i].m1, M=pd[i].m2;
        for (int j=i+1; j<n1; j++)
            if (pd[j].m1<=M && pd[j].m2>=m)
            {
                m=max(m,pd[j].m1);
                i=j;
            }
            else break;
    }
}

int main()
{
    freopen ("rays.in","r",stdin);
    freopen ("rays.out","w",stdout);
    citire();
    sort(pd,pd+n1,cmp);
    sort(ps,ps+n2,cmp);
    frigidere(pd,n1);
    frigidere(ps,n2);
    printf ("%d\n",f);
    return 0;
}