Cod sursa(job #1145565)

Utilizator Barcau_EmanuelBarcau Emanuel Barcau_Emanuel Data 18 martie 2014 12:00:06
Problema Rays Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include<fstream>
#include<algorithm>
using namespace std;
ifstream f("rays.in");
ofstream g("rays.out");
long long n,k1,k2,m,i,j,rez,aux;

struct pie{
long long x,y1,y2;}a[2000002],b[2000002],x,y;

int cmp(pie a,pie b)
{
    return (long long)a.x*b.y2>(long long)b.x*a.y2;
}

void fct(long long k,pie v[],long long &rez)
{
    long long i,j;
    sort(v+1,v+k+1,cmp);
    if(k>0)
    {
        rez++;
        long long x=v[1].x;
        long long y=v[1].y2;
        for(i=2;i<=k;i++)
        {
            if(x*v[i].y1>y*v[i].x)
            {
                rez++;
                x=v[i].x;
                y=v[i].y2;
            }
        }
    }
}

int main()
{
    f>>n;
    for(i=1;i<=n;i++)
    {
        f>>x.x>>x.y1>>x.y2;
        if(x.y1>x.y2)
        {
            aux=x.y1;
            x.y1=x.y2;
            x.y2=aux;
        }
        if(x.x<0)
        {
            x.x=-x.x;
            k2++;
            b[k2]=x;
        }
        else
        {
            k1++;
            a[k1]=x;
        }
    }

    fct(k1,a,rez);
    fct(k2,b,rez);
    g<<rez;

    return 0;
}