Cod sursa(job #2749991)

Utilizator Alexandru_GaloiuAlexandru Galoiu Alexandru_Galoiu Data 9 mai 2021 11:29:43
Problema Rays Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.13 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 SEGM
{
    double p1,p2;
}dr[200001],st[200001];
bool cmp(SEGM a,SEGM b)
{
    if(a.p2>b.p2||(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)
    {
        double x,y1,y2;
        cin>>x>>y1>>y2;
        double u1=y1/x,u2=y2/x;
        if(x<=0)
        {
            st[++ks].p1=min(u1,u2);
            st[ks].p2=max(u1,u2);
        }
        else
        {
            dr[++kd].p1=min(u1,u2);
            dr[kd].p2=max(u1,u2);
        }
    }
    sort(st+1,st+ks+1,cmp);
    sort(dr+1,dr+kd+1,cmp);
    double last=st[1].p2;
    int rays=1;
    for(int i=2;i<=ks;++i)
        if(last<st[i].p1)
        {
            last=st[i].p2;
            ++rays;
        }
    last=dr[1].p2;
    ++rays;
    for(int i=2;i<=kd;++i)
        if(last<dr[i].p1)
        {
            last=dr[i].p2;
            ++rays;
        }
    cout<<rays;
    return 0;
}