Cod sursa(job #2405194)

Utilizator MoldovanAndrei1Moldovan Andrei MoldovanAndrei1 Data 14 aprilie 2019 08:54:55
Problema Rays Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.25 kb
#include <bits/stdc++.h>
using namespace std;
struct dd
{
    int x,y,z;
};
const double eps=1.e-14;
dd cadr[200005];
dd cadr1[200005];
struct adj
{
    double panta,panta1;
};
adj v[200005];
bool cmp(adj a,adj b)
{
    if(fabs(a.panta1-b.panta1)<=eps)
    {if(a.panta-b.panta<=-1*eps)
        return 1;
    return 0;
    }
    if(a.panta1-b.panta1<=eps)
        return 1;
    return 0;
}
const int sz=1<<16;
int pz=sz-1;
char buffer[sz];
char ad()
{
    ++pz;
    if(pz==sz)
    {
        pz=0;
        fread(buffer,1,sz,stdin);
    }
    return buffer[pz];
}
int form()
{
    char ch=ad();
    while(!(ch=='-'||(ch>='0'&&ch<='9')))
        ch=ad();
    int nr1=0,s1=1;
    if(ch=='-'){s1=-1;ch=ad();}
while(ch>='0'&&ch<='9')
{
    nr1=nr1*10+ch-'0';
    ch=ad();
}
return nr1*s1;
}
int main()
{
    freopen("rays.in","r",stdin);
    freopen("rays.out","w",stdout);
    int n, i ,cnt1=0,cnt2=0;
    n=form();
    for(i=1;i<=n;++i)
    {
        dd a;
        a.z=form();a.x=form();a.y=form();
        if(a.z<0)
        cadr[++cnt1]=a;
        else
            cadr1[++cnt2]=a;
    }
    for(i=1;i<=cnt1;++i)
    {
        v[i].panta=atan2(-1*cadr[i].z,cadr[i].x);
     v[i].panta1=atan2(-1*cadr[i].z,cadr[i].y);
     double a1=v[i].panta;
     double b1=v[i].panta1;
     if(a1-b1>=eps)
        v[i].panta=1,v[i].panta1=a1;
    }
    sort(v+1,v+cnt1+1,cmp);
    int cnt=(cnt1>=1);
    adj a=v[1];
    for(i=2;i<=cnt1;++i)
    {
        if(v[i].panta-a.panta1>=eps)
        {
            cnt++;
            a=v[i];
            continue;
        }
        if(a.panta-v[i].panta<=-1*eps)a.panta=v[i].panta;
    }
    for(i=1;i<=cnt2;++i)
    {
        v[i].panta=atan2(cadr1[i].z,-1*cadr1[i].x);
     v[i].panta1=atan2(cadr1[i].z,-1*cadr1[i].y);
     double a1=v[i].panta;
     double b1=v[i].panta1;
     if(a1-b1>=eps)
        v[i].panta=b1,v[i].panta1=a1;
    }
    sort(v+1,v+cnt2+1,cmp);
    int cnt3=(cnt2>=1);
    a=v[1];
    for(i=2;i<=cnt2;++i)
    {
        if(v[i].panta-a.panta1>=eps)
        {
            cnt3++;
            a=v[i];
            continue;
        }
        if(a.panta-v[i].panta<=-1*eps)a.panta=v[i].panta;
    }
    printf("%d\n",cnt+cnt3);
    return 0;

}