Cod sursa(job #1754243)

Utilizator alexandra_udristoiuUdristoiu Alexandra Maria alexandra_udristoiu Data 7 septembrie 2016 18:45:50
Problema Rays Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.75 kb
#include<fstream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#define DIM 400005
#define DIM1 1000000
using namespace std;
int n, i, a, b, c, sol, nrs, nrd, r;
int cd[DIM], f[DIM / 2];
char s[DIM1 + 5];
struct str{
    int x;
    int y;
    int t;
    int ii;
};
str v[2][DIM];
FILE * fin = fopen("rays.in", "r");
FILE * fout = fopen("rays.out", "w");
int num(){
    while( (s[r] < '0' || s[r] > '9') && s[r] != '-'){
        r++;
        if(r == DIM1){
            r = 0;
            fread(s, 1, DIM1, fin);
        }
    }
    int x = 0, ok = 0;
    if(s[r] == '-'){
        ok = 1;
        r++;
    }
    while(s[r] >= '0' && s[r] <= '9'){
        x = x * 10 + s[r] - '0';
        r++;
        if(r == DIM1){
            r = 0;
            fread(s, 1, DIM1, fin);
        }
    }
    if(ok == 1){
        x = -x;
    }
    return x;
}
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(){
    fread(s, 1, DIM1, fin);
    n = num();
    for(i = 1; i <= n; i++){
        a = num();
        b = num();
        c = num();
        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 * nrd - 1].x = v[1][2 * nrd].x = a;
            v[1][2 * nrd - 1].ii = v[1][2 * nrd].ii = i;
            v[1][2 * nrd - 1].y = b;
            v[1][2 * nrd].y = c;
            v[1][2 * nrd - 1].t = 0;
            v[1][2 * nrd].t = 1;
        }
    }
    ff(0, nrs);
    ff(1, nrd);
    fprintf(fout, "%d\n", sol);
    return 0;
}