Cod sursa(job #1754225)

Utilizator alexandra_udristoiuUdristoiu Alexandra Maria alexandra_udristoiu Data 7 septembrie 2016 18:07:08
Problema Rays Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.1 kb
#include<fstream>
#include<algorithm>
#include<cstring>
#define DIM 400005
using namespace std;
int n, i, a, b, c, sol, nrs, nrd;
int cd[DIM], f[DIM / 2];
struct str{
    int x;
    int y;
    int t;
    int ii;
};
str v[2][DIM];
ifstream fin("rays.in");
ofstream fout("rays.out");
int cadran(int x, int y){
    if(y >= 0){
        return 0;
    }
    return 1;
}
long long det(int X1, int Y1, int X2, int Y2){
    return X1 * 1LL * Y2 - X2 * 1LL * Y1;
}
long long dist(int x, int y){
    return x * 1LL * x + y * 1LL * y;
}
int cmp(str a, str b){
    int c1 = cadran(a.x, a.y);
    int c2 = cadran(b.x, b.y);
    if(c1 != c2){
        return c1 < c2;
    }
    long long d = det(a.x, a.y, b.x, b.y);
    if(d != 0){
        return d > 0;
    }
    return dist(a.x, a.y) < dist(b.x, b.y);
}
void ff(int tt, int nr){
    int u = 0, i;
    nr *= 2;
    memset(f, 0, sizeof(f));
    sort(v[tt] + 1, v[tt] + nr + 1, cmp);
    for(i = 1; i <= nr; i++){
        if(v[tt][i].t == 0){
            u++;
            cd[u] = v[tt][i].ii;
        }
        else{
            if(f[ v[tt][i].ii ] == 0){
                sol++;
                while(u > 0){
                    f[ cd[u] ] = 1;
                    u--;
                }
            }
        }
    }
}
int main(){
    fin>> n;
    for(i = 1; i <= n; i++){
        fin>> a >> b >> c;
        if(b > c){
            swap(b, c);
        }
        if(a < 0){
            nrs++;
            v[0][2 * nrs - 1].x = v[0][2 * nrs].x = -a;
            v[0][2 * nrs - 1].ii = v[0][2 * nrs].ii = i;
            v[0][2 * nrs - 1].y = b;
            v[0][2 * nrs].y = c;
            v[0][2 * nrs - 1].t = 0;
            v[0][2 * nrs].t = 1;
        }
        else{
            nrd++;
            v[1][2 * nrs - 1].x = v[0][2 * nrs].x = a;
            v[1][2 * nrs - 1].ii = v[0][2 * nrs].ii = i;
            v[1][2 * nrs - 1].y = b;
            v[1][2 * nrs].y = c;
            v[1][2 * nrs - 1].t = 0;
            v[1][2 * nrs].t = 1;
        }
    }
    ff(0, nrs);
    ff(1, nrd);
    fout<< sol <<"\n";
    return 0;
}