Cod sursa(job #848521)

Utilizator stoicatheoFlirk Navok stoicatheo Data 5 ianuarie 2013 15:36:10
Problema Rays Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.6 kb
#include <fstream>
#include <cmath>
#include <algorithm>
#include <vector>
 
using namespace std;
 
const char InFile[]="rays.in";
const char OutFile[]="rays.out";
const int MaxN=200111;
const double PI=3.1415926535897932384626433832795;
const double RAD2DEG=180/PI;
const double INF=1e32;
 
ifstream fin(InFile);
ofstream fout(OutFile);
 
struct Inter
{
    Inter(double st=0.0, double dr=0.0):st(st),dr(dr){}
 
    double st,dr;
};
 
struct Inter_CMP
{
    inline bool operator() (const Inter &A, const Inter &B)
    {
        return A.st<B.st;
    }
};
 
int N,sol,done[MaxN],leftYind=-1,rightYind=-1;
int mx,my1,my2;
double st,dr;
Inter leftY[MaxN],rightY[MaxN];
 
inline void Solve(Inter *V,int length)
{
    sort(V,V+length,Inter_CMP());
    double right=-INF;
    for(register int i=0;i<length;++i)
    {
        if(V[i].st>right)
        {
            ++sol;
            right=V[i].dr;
        }
        else
        {
            right=min(right,V[i].dr);
        }
    }
}
 
int main()
{
    fin>>N;
    for(register int i=1;i<=N;++i)
    {
        fin>>mx>>my1>>my2;
        st=(double)my1/mx;
        dr=(double)my2/mx;
        if(st>dr)
        {
            swap(st,dr);
        }
        if(mx<0)
        {
            st=-st;
            dr=-dr;
            swap(st,dr);
            leftY[++leftYind]=Inter(st,dr);
        }
        else
        {
            rightY[++rightYind]=Inter(st,dr);
        }
    }
    fin.close();
 
    Solve(leftY,leftYind+1);
    Solve(rightY,rightYind+1);
 
    fout<<sol;
    fout.close();
    return 0;
}