Cod sursa(job #1714320)

Utilizator enacheionutEnache Ionut enacheionut Data 7 iunie 2016 22:36:41
Problema Rays Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <fstream>
#include <algorithm>
 
using namespace std;
 
ifstream fin("rays.in");
ofstream fout("rays.out");
 
long long n, nr, nrSt, nrDr;
 
struct segment{
    long long x;
    long long y1;
    long long y2;
 
}v[200010], st[200010], dr[200010];
 
int cmp(segment a, segment b)
{
    return a.y2 * b.x < a.x * b.y2;
}
 
void solve(long long n, segment v[]){
 
    long long capA, capB;
 
    if(n == 0)
        return;
 
    sort(v + 1, v + n + 1, cmp);
 
    nr ++;
 
    capA = v[1].x;
    capB = v[1].y2;
 
    for(long long i = 1; i <= n; i ++)
    {
        if(v[i].x * capB < v[i].y1 * capA )
        {
            nr ++;
            capA = v[i].x;
            capB = v[i].y2;
        }
    }
 
}
 
int main()
{
    fin >> n;
 
    for(long long i = 1; i <= n; i ++)
    {
        fin >> v[i].x >> v[i].y1 >> v[i].y2;
 
        if(v[i].y1 > v[i].y2)
        {
            swap(v[i].y1, v[i].y2);
        }
 
        if(v[i].x < 0)
        {
            st[++nrSt] = v[i];
            st[nrSt].x = -v[i].x;
 
        }
        else
        {
            dr[++nrDr] = v[i];
        }
    }
 
    solve(nrSt,st);
    solve(nrDr,dr);
 
    fout << nr;
 
    return 0;
}