Cod sursa(job #1523737)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 13 noiembrie 2015 09:03:26
Problema Rays Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.06 kb
#include <cstdio>
#include <algorithm>
#include <cctype>
#define MAXN 200000
#define BUF_SIZE 4096
struct mycreation{
    int a, x, y;
};
mycreation v[MAXN], u[MAXN];
int pos=BUF_SIZE;
char buf[BUF_SIZE];
FILE *fin;
inline char nextch(){
    if(pos==BUF_SIZE){
        fread(buf, BUF_SIZE, 1, fin);
        pos=0;
    }
    return buf[pos++];
}
inline int read(){
    int x=0, s=1;
    char ch=nextch();
    while((!isdigit(ch))&&(ch!='-')){
        ch=nextch();
    }
    if(ch=='-'){
        s=-1;
        ch=nextch();
    }
    while(isdigit(ch)){
        x=10*x+ch-'0';
        ch=nextch();
    }
    return x*s;
}
bool cmp(const mycreation a, const mycreation b){
    return a.a*(long long)b.x>b.a*(long long)a.x;
}
inline bool check(int x1, int y1, int x2, int y2){
    return x1*(long long)y2<=x2*(long long)y1;
}
inline int solve(mycreation v[], int n){
    int ans, i, x, y;
    std::sort(v, v+n, cmp);
    ans=0;
    i=0;
    while(i<n){
        ans++;
        x=v[i].a;
        y=v[i].y;
        i++;
        while((i<n)&&(check(x, y, v[i].a, v[i].x))){
            if(check(x, y, v[i].a, v[i].y)){
                x=v[i].a;
                y=v[i].y;
            }
            i++;
        }
    }
    return ans;
}
int main(){
    int n, m, k, i, a, aux;
    FILE *fout;
    fin=fopen("rays.in", "r");
    fout=fopen("rays.out", "w");
    n=read();
    m=k=0;
    for(i=0; i<n; i++){
        a=read();
        if(a>0){
            v[k].a=a;
            v[k].x=read();
            v[k].y=read();
            if(v[k].x>v[k].y){
                aux=v[k].x;
                v[k].x=v[k].y;
                v[k].y=aux;
            }
            k++;
        }else{
            u[m].a=-a;
            u[m].x=read();
            u[m].y=read();
            if(u[m].x>u[m].y){
                aux=u[m].x;
                u[m].x=u[m].y;
                u[m].y=aux;
            }
            m++;
        }
    }
    fprintf(fout, "%d\n", solve(v, k)+solve(u, m));
    fclose(fin);
    fclose(fout);
    return 0;
}