Cod sursa(job #573972)

Utilizator Sm3USmeu Rares Sm3U Data 6 aprilie 2011 18:39:44
Problema Rays Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.22 kb
#include <stdio.h>
#include <cmath>
#include <algorithm>

using namespace std;

struct ceva
{
    double y1;
    double y2;
}dreapta[200100],stanga[200100],liniStanga[200100],liniDreapta[200100];

int n;
int istanga;
int idreapta;
int s;

bool cmp(ceva x, ceva y)
{
    if(x.y2>y.y2)
        return false;
    return true;
}


void citire()
{
    scanf("%d",&n);
    for(int i=0;i<n;++i)
    {
        double x;
        double y1;
        double y2;
        scanf("%lf %lf %lf",&x,&y1,&y2);
        if(y2<y1)
        {
            int aux=y2;
            y2=y1;
            y1=aux;
        }
        if(x>0)
        {
            if(y2/x <y1/x)
            {
                dreapta[idreapta].y1=y1/x;
                dreapta[idreapta].y2=y2/x;
            }
            else
            {
                dreapta[idreapta].y1=y2/x;
                dreapta[idreapta].y2=y1/x;
            }
            idreapta++;
        }
        else
        {
            x*=-1;
            if(y2/x < y1/x)
            {
                stanga[istanga].y1=y1/x;
                stanga[istanga].y2=y2/x;
            }
            else
            {
                stanga[istanga].y1=y2/x;
                stanga[istanga].y2=y1/x;
            }

            istanga++;
        }

    }
}

void verf(ceva x,ceva linii[], int &m)
{
    for(int i=0;i<m;i++)
    {
        if(x.y1<=linii[i].y1 && x.y2>=linii[i].y2)
        {

            linii[i].y1=x.y1;
            linii[i].y2=x.y2;
            return;
        }
        else
        if(x.y2>=linii[i].y2 && x.y2<=linii[i].y1)
        {
            linii[i].y2=x.y2;
            return;
        }

    }
    linii[m].y1=x.y1;
    linii[m++].y2=x.y2;
    s++;
    return;
}

void linii(ceva unghiuri[],ceva linii[],int n)
{
    int m=0; // lungime linii;
    for(int i=0;i<n;i++)
    {
        verf(unghiuri[i],linii,m);
    }
}

int main()
{
    freopen("rays.in","r",stdin);
    freopen("rays.out","w",stdout);
    citire();
    sort(dreapta,dreapta+idreapta,cmp);
    sort(stanga,stanga+istanga,cmp);
    linii(dreapta,liniDreapta,idreapta);
    linii(stanga,liniStanga,istanga);
    printf("%d\n",s);
    return 0;
}