Cod sursa(job #2749977)

Utilizator Alexandru_GaloiuAlexandru Galoiu Alexandru_Galoiu Data 9 mai 2021 11:11:50
Problema Rays Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.68 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream cin("rays.in");
ofstream cout("rays.out");
struct POINT
{
    double x,y;
};
struct SEGM
{
    double p1,p2;
}dr[200001],st[200001];
bool cmp(SEGM a,SEGM b)
{
    if(a.p2>b.p2)
        return 0;
    else if(a.p1>b.p1&&a.p2==b.p2)
        return 0;
    return 1;
}
int main()
{
    int n,ks=0,kd=0;
    cin>>n;
    for(int i=1;i<=n;++i)
    {
        POINT P1,P2;
        cin>>P1.x>>P1.y>>P2.y;
        P2.x=P1.x;
        double u1,u2;
        u1=P1.y/P1.x;
        u2=P2.y/P2.x;
        if(P1.x<=0)
        {
            if(u1<u2)
            {
                st[++ks].p1=u1;
                st[ks].p2=u2;
            }
            else
            {
                st[++ks].p1=u2;
                st[ks].p2=u1;
            }
        }
        else
        {
            if(u1<u2)
            {
                dr[++ks].p1=u1;
                dr[ks].p2=u2;
            }
            else
            {
                dr[++ks].p1=u2;
                dr[ks].p2=u1;
            }
        }
    }
    sort(st+1,st+ks+1,cmp);
    sort(dr+1,dr+kd+1,cmp);
//    for(int i=1;i<=ks;i++)
//        cout<<st[i].p1<<" "<<st[i].p2<<'\n';
//    cout<<'\n';
//    for(int i=1;i<=kd;i++)
//        cout<<dr[i].p1<<" "<<dr[i].p2<<'\n';
    int last=1,rays=1;
    for(int i=2;i<=ks;++i)
        if(st[last].p2<st[i].p1)
        {
            last=i;
            rays++;
        }
    last=1;
    //cout<<rays<<" ";
    rays++;

    for(int i=2;i<=kd;++i)
        if(dr[last].p2<dr[i].p1)
        {
            last=i;
            rays++;
        }
    cout<<rays;
    return 0;
}