Cod sursa(job #950182)

Utilizator enedumitruene dumitru enedumitru Data 16 mai 2013 00:41:10
Problema Rays Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
 
#define pb push_back
#define sz(c) int((c).size())
#define all(c) (c).begin(), (c).end()
 
typedef struct Segment {
    int x, y1, y2;
} Segment;
 
int ret;
vector<Segment> v, u;
 
void ReadData() {
    freopen("rays.in", "r", stdin);
    freopen("rays.out", "w", stdout);
 
    int N;
    for (scanf("%d", &N); N; --N) {
        Segment tmp;
        scanf("%d %d %d", &tmp.x, &tmp.y1, &tmp.y2);
 
        if (tmp.y1 > tmp.y2) tmp.y1 ^= tmp.y2 ^= tmp.y1 ^= tmp.y2;
 
        if (tmp.x > 0) v.pb(tmp);
        else {
            tmp.x *= -1;
            u.pb(tmp);
        }
    }
}
 
int cross(int X1, int Y1, int X2, int Y2) {
    long long P = (long long)X1*Y2 - (long long)X2*Y1;
    if (P == 0) return 0;
    return P > 0 ? 1 : -1;
}
 
inline int cmp(Segment a, Segment b) {
    return cross(a.x, a.y2, b.x, b.y2) == 1;
}
 
void Solve(vector<Segment> &v) {
    sort(all(v), cmp);
    if (!sz(v)) return;
 
    int X = v[0].x;
    int Y = v[0].y2;
    ++ret;
 
    for (int i = 1; i < sz(v); ++i)
        if (cross(X, Y, v[i].x, v[i].y1) == 1) {
            ++ret;
            X = v[i].x;
            Y = v[i].y2;
        }
}
 
int main() {
    ReadData();
    Solve(v);
    Solve(u);
    printf("%d\n", ret);
}