Cod sursa(job #118482)

Utilizator pauldbPaul-Dan Baltescu pauldb Data 26 decembrie 2007 00:15:19
Problema Rays Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.6 kb
#include <stdio.h>
#include <algorithm>

using namespace std;

#define maxn 200010
#define inf 1000000001

int n,m,l,sol;
int a1[maxn],a2[maxn],b1[maxn],b2[maxn],c1[maxn],c2[maxn],p[maxn];

//7 * 4 * 2 * 10^5 

int cmp(int i,int j)
{
    return 1LL * c1[i] * a1[j] < 1LL * c1[j] * a1[i];
}

int cmp2(int i,int j)
{
    return 1LL * c2[i] * a2[j] < 1LL * c2[j] * a2[i];
}

int solve(int a[],int b[],int c[],int n)
{
    int i,rez=0, lx ,ly;
    
    if (a[1] < 0) lx = -1, ly = inf;
    else lx = 1, ly = -inf;
    
    for (i=1;i<=n;i++) 
    {
        if (1LL * ly * a[p[i]] < 1LL * b[p[i]] * lx)
        {
            rez++;
            lx = a[p[i]];
            ly = c[p[i]];
        }
    }
  
    return rez;
}

inline void swap(int &x,int &y)
{
    int aux=x;
    x=y;
    y=aux;
}

int main()
{
    freopen("rays.in","r",stdin);
    freopen("rays.out","w",stdout);
    
    scanf("%d ",&n);
    
    int i,x,y,z,aux;
    
    for (i=1;i<=n;i++)
    {
        scanf("%d %d %d ",&x,&y,&z);
        
        if (x<0)
        {    
            if (z>y) swap(y,z);
            
            m++;
            a1[m] = x, b1[m] = y, c1[m] = z;        
        }
        else {       
                 if (z<y) swap(y,z);
                 l++;
                 a2[l] = x, b2[l] = y, c2[l] = z;
             }
    }
    
    for (i=1;i<=m;i++) p[i]=i;
    sort(p+1,p+m+1,cmp);
    sol += solve(a1,b1,c1,m);
            
    for (i=1;i<=l;i++) p[i]=i;
    sort(p+1,p+l+1,cmp2);
    sol += solve(a2,b2,c2,l);
    
    printf("%d\n",sol);
    
    return 0;
}