Cod sursa(job #1518734)

Utilizator qcataMihai Catalin qcata Data 6 noiembrie 2015 11:12:11
Problema Rays Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.66 kb
#include<fstream>
#include<iostream>
#include<algorithm>
using namespace std;
 
ifstream filein("rays.in");
ofstream fileout("rays.out");
 
#define MAX 200001
#define swap(t,a,b)(t=a,a=b,b=t)

int N, k=0, kk=0;
 
	struct Segment
		{
   		 int x;
    	 double y1,y2;
		}rightSide[MAX],leftSide[MAX];;

	int testsort(Segment a, Segment b)
       {
   			 if( a.y2 < b.y2)
	 		   return 1;
	 		 else
	  		   return 0;   
       }
 
 
int main()
{
    filein>>N;
    int x, y1, y2,t,bullet = 1,j = 1;
    
    while (filein >> x >> y1 >> y2)
    {
       if (x > 0)
        {
            rightSide[++k].x = x;
            if (y1 > y2)
                swap(t, y1, y2);
            rightSide[k].y1 = (double)y1 / x;
            rightSide[k].y2 = (double)y2 / x;
        }
        else
        {
            leftSide[++kk].x = x;
            if (y1 > y2)
                swap(t, y1, y2);
            leftSide[kk].y1 = (double)y1 / x;
            leftSide[kk].y2 = (double)y2 / x;
        }
         
    }

       sort(rightSide+1, rightSide+k+1, testsort);
    		for (int i = 2;i <= k;++i)
    			{
       			  if (rightSide[i].y1 > rightSide[j].y2)
       		        {
         			   ++bullet;
         			   j = i;
       			    }
   			    }
   			    
    sort(leftSide+1, leftSide+kk+1, testsort);
    		j=1;
    		++bullet;
    		for (int i = 2;i <= kk;++i)
   				 {
    			    if (leftSide[i].y2 > leftSide[j].y1)
      				  {
           				 ++bullet;
          				 j = i;
       				  }
    			 }
    			 
    fileout << bullet;
    fileout.flush();
    fileout.close();
    filein.close();
    return 0;

}