Cod sursa(job #182493)

Utilizator Mishu91Andrei Misarca Mishu91 Data 20 aprilie 2008 22:47:23
Problema Rays Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.61 kb
#include <cstdio>
#include <algorithm>
#include <vector>

#define eps 0.000001
#define Nmax 200000
using namespace std;

inline double min(double a, double b)
{
  return (b - a > eps)? a : b;
}

inline double max(double a, double b)
{
  return (b - a > eps)? b : a;
}

struct pant{double li, lf;}v1[Nmax],  v2[Nmax];

int nr1,nr2;

void citire()
{
  int N,x,y1,y2;
  pant p;
  
  scanf("%d",&N);
  
  for(int i=0; i<N; i++)
  {
    scanf("%d %d %d",&x,&y1,&y2);
    if(y1 > y2)
      swap(y1,y2);
    
    if(x > 0)
    {
      v1[nr1].li = (double)y1/x;
      v1[nr1++].lf = (double)y2/x;
    }
    
    else
    {
      v2[nr2].li = (double)y1/x;
      v2[nr2++].lf = (double)y2/x;
    }
  }
}

struct cmp
{
  bool operator()(const pant &a, const pant &b)
  {
    return (b.li - a.li > eps) || (b.li - a.li < eps && b.lf - a.lf > eps);
  }
};

int solve(pant v[Nmax],int nrv)
{
  int nr = 0;
  sort(v,v + nrv,cmp());
  
  pant p[Nmax];
  
  for(int i=0; i<nrv; i++)
  {
    if(nr == 0)
    {
      p[nr++] = v[i];
      continue;
    }
    
    bool ok = false;
    
    for(int j = 0; j<nr; j++)
    {
      if(p[j].li - v[i].lf > eps) continue;
      if(v[i].li - p[j].lf > eps) continue;
      
      ok = true;
      
      p[j].li = max(v[i].li, p[j].li);
      p[j].lf = min(v[j].lf, p[j].lf);
      
    }
    
    if(!ok)
      p[nr++] = v[i];
  }
  
  return nr;
  
}

int main()
{
  freopen("rays.in","r",stdin);
  freopen("rays.out","w",stdout);
  
  citire();
  int x = solve(v1,nr1) ;
  int y = solve(v2,nr2);
  printf("%d",x+y);
}