Cod sursa(job #2405981)

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

using namespace std;
const double PI=2.0*acos(0.0);
const double eps=1e-18;
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.p2-aux.p1<-eps)
        swap(aux.p1,aux.p2);
    return aux;
}
segment intersect(segment a,segment b)
{
    if(a.p2-b.p1<-eps||a.p1-b.p2>eps)
        return nul;
    if(b.p1-a.p2<-eps)
        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(1.0*(-x)*sin90+1.0*y1*cos90,1.0*x*cos90+1.0*y1*sin90);
            aux.p2=atan2(1.0*(-x)*sin90+1.0*y2*cos90,1.0*x*cos90+1.0*y2*sin90);
        }
        else
        {
            aux.p1=atan2(1.0*y1,1.0*x);
            aux.p2=atan2(1.0*y2,1.0*x);
        }
        if(aux.p2-aux.p1<-eps)
            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;
}