Cod sursa(job #160565)

Utilizator RobytzzaIonescu Robert Marius Robytzza Data 16 martie 2008 10:55:36
Problema Rays Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.18 kb
#include <stdio.h>
#define MAX 500000

struct puncte
{
  float x1,y1,y2;
};

struct pan
{
   float min,max;
};

puncte stanga[MAX],dreapta[MAX];
pan sir[MAX];

int nrs,nrd,k,numar,n;

void citire()
{
   scanf ("%d",&n);
   float x;
   for (int i=0;i<n;i++)
   {
     scanf ("%f",&x);
      if (x>=0)
      {
	dreapta[nrd].x1=x;
	scanf ("%f%f",&dreapta[nrd].y1,&dreapta[nrd].y2);
	nrd++;
      }
      else
      {
	stanga[nrs].x1=x;
	scanf ("%f%f",&stanga[nrs].y1,&stanga[nrs].y2);
	nrs++;
      }
   }
}


float minim (float a,float b)
{
  return a<b?a:b;
}

float maxim (float a,float b)
{
  return a>b?a:b;
}

void calcul (puncte lol[MAX],int nr)
{
  for (int i=0;i<nr;i++)
  {
     if (lol[i].x1==0)
     {
	sir[i].max=1000;
	sir[i].min=1000;
     }
     else
     {
       float x=(minim(lol[i].y1,lol[i].y2))/(lol[i].x1);
       float y=(maxim(lol[i].y1,lol[i].y2))/(lol[i].x1);
       sir[i].min=minim(x,y);
       sir[i].max=maxim(x,y);
     }
  }
}

void poz (int li,int ls,int &k,pan a[MAX])
{
   int i=li,j=ls,i1=0,j1=-1,c;
   pan aux;
   while (i<j)
   {
     if (a[i].max<a[j].max)
     {
       aux=a[i];
       a[i]=a[j];
       a[j]=aux;
       c=i1;
       i1=-j1;
       j1=-c;
     }
     else
       if (a[i].max==a[j].max)
       if (a[i].min<a[j].min)
       {
       aux=a[i];
       a[i]=a[j];
       a[j]=aux;
       c=i1;
       i1=-j1;
       j1=-c;
       }
     i+=i1;
     j+=j1;
   }
   k=i;
}

void qsort (int li,int ls)
{
   if (li<ls)
   {
     poz (li,ls,k,sir);
     qsort (li,k-1);
     qsort (k+1,ls);
   }
}

void numarare (int nr)
{
    float m,M;
   for (int i=0;i<nr;i++)
   {
      numar++;
      m=sir[i].min,M=sir[i].max;
      for (int j=i+1;j<nr;j++)
      {
	if (sir[j].max<=M && sir[j].max>=m)
	{
	  m=maxim(m,sir[j].min);
	  i=j;
	}
	else
	{
	  break;
	}
      }
   }
}

int main ()
{
  freopen ("rays.in","r",stdin);
  freopen ("rays.out","w",stdout);
  citire();
  calcul(dreapta,nrd);
  k=0;
  qsort(0,nrd-1);
  numarare(nrd);
  calcul(stanga,nrs);
  k=0;
  qsort(0,nrs-1);
  numarare(nrs);
  printf ("%d",numar);
  return 0;
}