Cod sursa(job #923434)

Utilizator alecsandrualex cuturela alecsandru Data 23 martie 2013 16:08:01
Problema Rays Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.85 kb
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cstring>
#define eps 1.e-9;
using namespace std;
int x,y1,y2,rays,i,n;
struct tip1
{
    int i;
    double p;
};
tip1 t;
vector <tip1> v;
vector <tip1> v1;
int n1,n2;
bool cmp(const tip1 &a,const tip1 &b)
{
    return a.p-b.p<-eps;
}
int viz[200100],p[200100],rays2;
int main()
{
    freopen("rays.in","r",stdin);
    freopen("rays.out","w",stdout);
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%d%d%d",&x,&y1,&y2);
        if(x>0)
        {
            n1++;
            t.p=(double)y1/x;
            t.i=i;
            v.push_back(t);
            t.p=(double)y2/x;
            t.i=i;
            v.push_back(t);
        }
        if(x<0)
        {
            n2++;
            t.p=(double)y1/x;
            t.i=i;
            v1.push_back(t);
            t.p=(double)y2/x;
            t.i=i;
            v1.push_back(t);
        }
    }
    sort(v.begin(),v.end(),cmp);
    sort(v1.begin(),v1.end(),cmp);
    rays=1;
    for(i=0;i<2*n1;i++)
    {
        t=v[i];
        if(viz[t.i]==0)
        {
            viz[t.i]=rays;
        }
        else
        {
            if(p[viz[t.i]]==1)
            {
                continue;
            }
            else
            {
                rays++;
                p[viz[t.i]]=1;
            }
        }
    }
    memset(viz,0,2*n1);
    memset(p,0,2*n1);
    rays2=1;
    for(i=0;i<2*n2;i++)
    {
        t=v1[i];
        if(viz[t.i]==0)
        {
            viz[t.i]=rays;
        }
        else
        {
            if(p[viz[t.i]]==1)
            {
                continue;
            }
            else
            {
                rays2++;
                p[viz[t.i]]=1;
            }
        }
    }
    printf("%d",rays-1+rays2-1);
    return 0;
}