Cod sursa(job #1524208)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 13 noiembrie 2015 17:53:51
Problema Rays Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;

struct point {
    int x, y;

    point (int _x = 0, int _y = 0): x(_x), y(_y) {
        if (x < 0)
            x = -x;
    }
};

bool operator< (const point &a, const point &b) {
    return 1ll * a.y * b.x < 1ll * b.y * a.x;
}

struct segm {
    point st, dr;

    segm (point _st = point(0, 0), point _dr = point(0, 0)): st(_st), dr(_dr) {}
};

bool operator< (const segm &a, const segm &b) {
    return a.dr < b.dr;
}

vector <segm> segms_neg, segms_pos;

inline int solve (vector <segm> &segms) {
    if (segms.empty())
        return 0;

    sort(segms.begin(), segms.end());

    int ans = 1;
    point last = segms[0].dr;

    for (int i = 1; i < segms.size(); ++ i)
        if (last < segms[i].st) {
            ++ ans;
            last = segms[i].dr;
        }

    return ans;
}

int main()
{
    ifstream cin("rays.in");
    ofstream cout("rays.out");

    int n = 0;
    cin >> n;

    int x, y1, y2;
    for (int i = 1; i <= n; ++ i) {
        cin >> x >> y1 >> y2;

        if (y1 > y2)
            swap(y1, y2);

        if (x > 0)
            segms_pos.push_back(segm(point(x, y1), point(x, y2)));
        else
            segms_neg.push_back(segm(point(x, y1), point(x, y2)));
    }

    int ans = solve(segms_pos) + solve(segms_neg);
    cout << ans << '\n';

    cin.close();
    cout.close();
    return 0;
}