Cod sursa(job #2551151)

Utilizator Cojocaru_Andrei_CristianCojocaru Andrei Cristian Cojocaru_Andrei_Cristian Data 19 februarie 2020 16:27:25
Problema Rays Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.77 kb
#include <cstdio>
#include <algorithm>

using namespace std;
struct boi
{
    double x,y1,y2,panta1,panta2,stare;
}f[400005],v[400005];

int n,k,p;

bool mycmp1(boi a,boi b)
{
    return a.panta1<b.panta1;
}

bool mycmp2(boi a,boi b)
{
    return a.panta2<b.panta2;
}

int solve1()
{
    int cnt=0;
    sort(v+1,v+k+1,mycmp1);
    int start=1;
    for(int i=2;i<=k;i++)
    {
        if(v[start].panta2<v[i].panta1)
        {
            cnt++;
            start=i;
        }
        else
        {
            if(v[i].panta2<v[start].panta2)
            {
                start=i;
            }
        }
    }
    cnt++;
    return cnt;
}

int solve2()
{
    int cnt=0;
    sort(f+1,f+p+1,mycmp2);
    int start=1;
    for(int i=2;i<=p;i++)
    {
        if(f[start].panta1<f[i].panta2)
        {
            cnt++;
            start=i;
        }
        else
        {
            if(f[i].panta1<f[start].panta1)
            {
                start=i;
            }
        }
    }
    cnt++;
    return cnt;
}
int main()
{
    freopen("rays.in","r",stdin);
    freopen("rays.out","w",stdout);
    double x,y1,y2;
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
    {
        scanf("%lf%lf%lf",&x,&y1,&y2);
        if(x>=0)
        {
            v[++k].x=x;
            v[k].y1=min(y1,y2);
            v[k].y2=max(y2,y1);
            v[k].panta1=v[k].y1/v[k].x;
            v[k].panta2=v[k].y2/v[k].x;
        }
        else
        {
            f[++p].x=x;
            f[p].y1=min(y1,y2);
            f[p].y2=max(y2,y1);
            f[p].panta1=f[p].y1/f[p].x;
            f[p].panta2=f[p].y2/f[p].x;
        }
    }
    int cnt1=solve1();
    int cnt2=solve2();
    printf("%d",cnt1+cnt2);
    return 0;
}