Cod sursa(job #2017533)

Utilizator RaduMirceaAndreiRadu Mircea Andrei RaduMirceaAndrei Data 1 septembrie 2017 16:19:56
Problema Rays Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
# include <fstream>
# include <algorithm>
# define DIM 400010
# define a first.first
# define b first.second
# define c second
using namespace std;
ifstream fin("rays.in");
ofstream fout("rays.out");
pair<pair<int,int>,int> v[DIM];
int Marcat[DIM],s[DIM],n,x,y,z,i,j,k,u,nr;
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 main () {
    fin>>n;
    for(i=1;i<=n;i++){
        fin>>x>>y>>z;
        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;
}