Cod sursa(job #2405501)

Utilizator Alex_AeleneiAlex Aelenei Ioan Alex_Aelenei Data 14 aprilie 2019 16:18:18
Problema Rays Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.56 kb
#include <cmath>
#include <vector>
#include <cstdio>
#include <algorithm>

using namespace std;
const double PI=2.0*acos(0.0);
const double eps=1e-14;
const double sin90=sin(PI/2),cos90=cos(PI/2);
struct segment
{
    double p1,p2;
    void operator =(segment a)
    {
        p1=a.p1;
        p2=a.p2;
    }
    bool friend operator <(segment a,segment b)
    {
        if(fabs(a.p2-b.p2)<eps)
            return a.p1<b.p1;
        return a.p2<b.p2;
    }
    bool friend operator ==(segment a,segment b)
    {
        if(fabs(a.p1-b.p1)<eps&&fabs(a.p2-b.p2)<eps)
            return 1;
        return 0;
    }
    bool friend operator !=(segment a,segment b)
    {
        return !(a==b);
    }
};
segment nul;
vector <segment> v1,v2;
segment make_segment(double a,double b)
{
    segment aux;
    aux.p1=a;aux.p2=b;
    if(aux.p1>aux.p2)
        swap(aux.p1,aux.p2);
    return aux;
}
segment intersect(segment a,segment b)
{
    if(a.p2<b.p1||a.p1>b.p2)
        return make_segment(0.0,0.0);
    if(a.p2>b.p1)
        return make_segment(b.p1,a.p2);
    else
        return make_segment(a.p1,b.p2);
}
int main()
{
    freopen("rays.in","r",stdin);
    freopen("rays.out","w",stdout);
    int n,i,x,y1,y2,ans1=0,ans2=0;
    segment aux;
    scanf("%d",&n);
    nul=make_segment(0.0,0.0);
    for(i=1;i<=n;++i)
    {
        scanf("%d%d%d",&x,&y1,&y2);
        if(x>0)
        {
            aux.p1=atan2(-x*sin90+y1*cos90,x*cos90+y1*sin90);
            aux.p2=atan2(-x*sin90+y2*cos90,x*cos90+y2*sin90);
        }
        else
        {
            aux.p1=atan2(y1,x);
            aux.p2=atan2(y2,x);
        }
        if(aux.p1>aux.p2)
            swap(aux.p1,aux.p2);
        if(x<0)
            v1.push_back(aux);
        else
            v2.push_back(aux);
    }
    segment curin;
    if(v1.size())
    {
        sort(v1.begin(),v1.end());
        curin=v1[0];ans1=1;
        for(i=1;i<v1.size();++i)
        {
            aux=intersect(curin,v1[i]);
            if(aux!=nul)
                curin=aux;
            else
            {
                curin=v1[i];
                ++ans1;
            }
        }
    }
    if(v2.size())
    {
        sort(v2.begin(),v2.end());
        curin=v2[0];ans2=1;
        for(i=1;i<v2.size();++i)
        {
            aux=intersect(curin,v2[i]);
            if(aux!=nul)
                curin=aux;
            else
            {
                curin=v2[i];
                ++ans2;
            }
        }
    }
    printf("%d\n",ans1+ans2);
    return 0;
}