Cod sursa(job #1493701)

Utilizator CiurezAndreiCiurez Marius-Andrei CiurezAndrei Data 29 septembrie 2015 20:09:28
Problema Rays Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <fstream>
#include <algorithm>

using namespace std;

ifstream fin("rays.in");
ofstream fout("rays.out");

long long n, nr, nrSt, nrDr;

struct segment{
    int x;
    int y1;
    int 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(int 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;
}