Cod sursa(job #573943)

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

using namespace std;

const int M=200005;
int n, x, n1, n2, f, g, 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 (y1<=0)
                pd[n1].m1++;
            if (y2<=0)
                pd[n1].m2++;*/
            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 (y1>=0)
                ps[n2].m1++;
            if (y2>=0)
                ps[n2].m2++;*/
            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()
{
    for (int i=0; i<n1; i++)
    {
        double x=pd[i].m1, y=pd[i].m2, ok=0;
        for (int j=0; j<f; j++)
            if (a[j].x<=x && x>=a[j].y)
            {
                a[j].x=x;
                a[j].y=max(a[j].y,y);
                ok=1;
                break;
            }
            else if (a[j].x<=y && y>=a[j].y)
            {
                a[j].y=y;
                a[j].x=min(a[j].x,x);
                ok=1;
                break;
            }
        if (!ok)
        {
            a[f].x=x;
            a[f].y=y;
            f++;
        }
    }
    for (int i=0; i<n2; i++)
    {
        double x=ps[i].m1, y=ps[i].m2, ok=0;
        for (int j=0; j<g; j++)
            if (a[j].x>=x && x<=a[j].y)
            {
                a[j].y=y;
                a[j].x=min(a[j].x,x);
                ok=1;
                break;
            }
            else if (a[j].x>=y && y<=a[j].y)
            {
                a[j].x=x;
                a[j].y=min(a[j].y,y);
                ok=1;
                break;
            }
        if (!ok)
        {
            a[g].x=x;
            a[g].y=y;
            g++;
        }
    }
}

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