Cod sursa(job #828467)

Utilizator BarracudaFMI-Alex Dobrin Barracuda Data 3 decembrie 2012 20:10:10
Problema Rays Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
#include<fstream>
#include<algorithm>

const double inf=1LL<<32;
 
#define dim 200010
 
using namespace std;
ifstream f("rays.in");
ofstream g("rays.out");
 
int n,k,K;
 
struct  cub {
    double st,dr;
}A[dim],B[dim];
 
struct cmp{
    inline bool operator () ( const cub &a , const cub &b ){
        return a.st<b.st;
    }
};
int sol ( cub A [], int n ){
	
    int ans=0;
	double val=-inf;
	
	
    for (int i=1;i<=n;++i){
        if (A[i].st<=val){// daca intalnim un pct de intrare mai mare decat cel mai mare pct de iesire existent adaugam un glont
			
            if (A[i].dr<val){
                val=A[i].dr;
			}
			
		}
        else{
            ++ans;
			val=A[i].dr;
        }
    }
		
    return ans;
}
int main () {
	
	 
	
    f>>n;
	
    int x,y1,y2;
	
    for (int i=1;i<=n;++i ){
        f>>x>>y1>>y2;
        if(y1>y2){
			int aux=y1;
			y1=y2;
			y2=aux;
		}
        if (x>0){
            
            A[++k].st=(double)y1/x;
            A[k].dr=(double)y2/x;
        }
        else{
			x=-x;
            B[++K].st=(double)y1/x;
            B[K].dr=(double)y2/x;
        }
    }
     
    sort(A+1,A+k+1,cmp());
    sort(B+1,B+K+1,cmp());
     
    int rez=sol(A,k)+sol(B,K);
   
	g<<rez<<"\n";
	
 
    return 0;
}