Cod sursa(job #2406882)

Utilizator Alex_AeleneiAlex Aelenei Ioan Alex_Aelenei Data 16 aprilie 2019 12:13:09
Problema Rays Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.62 kb
#include <map>
#include <cmath>
#include <vector>
#include <cstdio>
#include <algorithm>

using namespace std;

struct s { double p; bool t; int id; };

const double pi = 2.0 * acos(0.0), e = 1e-14;

bool cmp(s a, s b) { if(fabs(a.p - b.p) < e) return a.t > b.t; return a.p - b.p < -e; };

vector<s> v;

const int mx = 3e6;
int p;

char b[mx];

int scan()
{
    int nr = 0, f = 1;
    while(b[p] != '-' and !('0' <= b[p] and b[p] <= '9')) { p++; if(p == mx) fread(b, 1, mx, stdin), p = 0; }
    if(b[p] == '-') { f = -1, p++; if(p == mx) fread(b, 1, mx, stdin), p = 0; }
    while('0' <= b[p] and b[p] <= '9') { nr = nr * 10 + b[p] - '0', p++; if(p == mx) fread(b, 1, mx, stdin), p = 0; }
    return f * nr;
}

map<int, bool> ve;

int main()
{
    freopen("rays.in", "r", stdin);
    freopen("rays.out", "w", stdout);
    int x, y1, y2, n, cnt = 0, ans = 0;
    bool t = 0;
    fread(b, 1, mx, stdin);
    n = scan();
    for(int i = 0; i < n; i++)
    {
        x = scan(), y1 = scan(), y2 = scan();
        if(y1 > y2) swap(y1, y2);
        v.push_back({atan2(y1, x) - pi / 2, 1, i});
        if(v.back().p <= e) v.back().p += 2 * pi;
        if(v.back().p - pi <= e) v.back().t = 0;
        v.push_back({atan2(y2, x) - pi / 2, 0, i});
        if(v.back().p <= e) v.back().p += 2 * pi;
        if(v.back().p - pi <= e) v.back().t = 1;
    }
    sort(v.begin(), v.end(), cmp);
    for(int i = 0; i < v.size(); i++)
    {
        if(v[i].t and !ve[v[i].id]) cnt++, t = 0, ve[v[i].id] = 1;
        else if(ve[v[i].id]) cnt--, ans += !t, t = 1, ve.clear();
    }
    printf("%d", ans);
    return 0;
}