Cod sursa(job #838499)

Utilizator misinozzz zzz misino Data 19 decembrie 2012 20:39:45
Problema Rays Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include<fstream>
#include<algorithm>
#define INF 1LL<<32
using namespace std;
ifstream f("rays.in");
ofstream g("rays.out");
int i,n,x,y1,y2,k,p;
struct ung{double li,ls;};
ung a[200100],b[200100];
bool cmp(ung a,ung b)
{
    return  a.li<b.li;
}
int sol(ung a[],int k)
{
    int i,sol=0;
    double val=-INF;
    for(i=1;i<=n;++i)
    if(a[i].li<=val)
    {
        if(a[i].ls<val)
        {
            val=a[i].ls;
        }
    }
    else
    {
        ++sol;
        val=a[i].ls;
    }
    return sol;
}
int main()
{
    f>>n;
    for(i=1;i<=n;++i)
    {
        f>>x>>y1>>y2;
        if(y1>y2)
        swap(y1,y2);
        if(x>0)
        {
            ++k;
            a[k].li=(double)y1/x;
            a[k].ls=(double)y2/x;
        }
        else
        {
            ++p;
            x=-x;
            b[p].li=(double)y1/x;
            b[p].ls=(double)y2/x;
        }
    }
    sort(a+1,a+k+1,cmp);
    sort(b+1,b+p+1,cmp);
    g<<sol(a,k)+sol(b,p);
    return 0;
}