Cod sursa(job #2749963)

Utilizator Alexandru_GaloiuAlexandru Galoiu Alexandru_Galoiu Data 9 mai 2021 10:40:25
Problema Rays Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.41 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream cin("rays.in");
ofstream cout("rays.out");
const double eps=1.0e-14;
const double INF=1e9;
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;
        if(P1.x<=0)
        {
            st[++ks].p1=min(P1.y/P1.x,P2.y/P2.x);
            st[ks].p2=max(P1.y/P1.x,P2.y/P2.x);
        }
        else
        {
            dr[++kd].p1=min(P1.y/P1.x,P2.y/P2.x);
            dr[kd].p2=max(P1.y/P1.x,P2.y/P2.x);
        }
    }
    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].p1>st[i].p2)
        {
            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;
}