Cod sursa(job #2017536)

Utilizator RaduMirceaAndreiRadu Mircea Andrei RaduMirceaAndrei Data 1 septembrie 2017 16:30:26
Problema Rays Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.9 kb
# include <fstream>
# include <cstdio>
# include <algorithm>
# define DIM 400010
# define NR 100010
# define a first.first
# define b first.second
# define c second
using namespace std;
FILE*fin=fopen("rays.in","r");
ofstream fout("rays.out");
pair<pair<int,int>,int> v[DIM];
char buff[NR];
int Marcat[DIM],s[DIM],n,x,y,z,i,j,k,u,nr,pp;
int cadran(int x,int y){
    if(x>0&&y<0)
        return 1;
    if(x>0&&y>=0)
        return 2;
    if(x<0&&y>=0)
        return 3;
    return 4;
}
bool cmp(pair<pair<int,int>,int> x,pair<pair<int,int>,int> y){
    if(cadran(x.a,x.b)==cadran(y.a,y.b)){
        if(1LL*x.a*y.b==1LL*x.b*y.a)
            return x.c<y.c;
        return 1LL*x.a*y.b>1LL*x.b*y.a;
    }
    return cadran(x.a,x.b)<cadran(y.a,y.b);
}
int citire(){
    int nr=0,semn;
    while((!(buff[pp]>='0'&&buff[pp]<='9'))&&buff[pp]!='-'){
        pp++;
        if(pp==NR)
            fread(buff,1,NR,fin);
    }
    if(buff[pp]=='-'){
        semn=-1;
        pp++;
        if(pp==NR)
            fread(buff,1,NR,fin);
    }
    else
        semn=1;
    while(buff[pp]>='0'&&buff[pp]<='9'){
        nr=nr*10+buff[pp]-'0';
        pp++;
        if(pp==NR)
            fread(buff,1,NR,fin);
    }
    return nr*semn;
}
int main () {
    fread(buff,1,NR,fin);
    n=citire();
    for(i=1;i<=n;i++){
        x=citire();
        y=citire();
        z=citire();
        if(x>0&&y>z)
            swap(y,z);
        if(x<0&&y<z)
            swap(y,z);
        v[++k].a=x;
        v[k].b=y;
        v[k].c=-i;
        v[++k].a=x;
        v[k].b=z;
        v[k].c=i;
    }
    sort(v+1,v+k+1,cmp);
    for(i=1;i<=k;i++){
        if(v[i].c<0||(v[i].c>0&&Marcat[v[i].c]==1))
            s[++u]=-v[i].c;
        else{
            nr++;
            for(j=1;j<=u;j++)
                Marcat[s[j]]=1;
            u=0;
        }
    }
    fout<<nr<<"\n";
    return 0;
}