Cod sursa(job #2761562)

Utilizator maria_neagoieMaria Neagoie maria_neagoie Data 2 iulie 2021 17:57:43
Problema Rays Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.06 kb
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int NMAX=200000,SIZEMAX=2*NMAX+5; //punem cate 2 pct (capetele) pt fiecare segm
pair <double,double> stanga[SIZEMAX],dreapta[SIZEMAX];
int nr_min(pair <double,double> unghi[SIZEMAX],int n)
{
    int cnt=0,i;
    double unghi_glont;
    unghi_glont=unghi[1].first-1;
    for(i=1;i<=n;i++)
    {
        if(unghi_glont<unghi[i].first) //glontul nu poate strapunge acest segment
        {
            cnt++;
            unghi_glont=unghi[i].second; //adaugam un nou glont - care trece prin capatul de sfarsit al segm a.i. obtinem unghi max
        }
        else //daca glontul ar putea strapunge segmentul, nu e nevoie de un glont nou,
            unghi_glont=min(unghi_glont,unghi[i].second); //ci il schimbam pe cel curent daca unghi_glont>unghi[i].second (pt a trece prin segment)
    }
    return cnt;
}
int main()
{
    freopen("rays.in","r",stdin);
    freopen("rays.out","w",stdout);
    int n,i,nr_st=0,nr_dr=0,rez;
    double x,y1,y2;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%lf%lf%lf",&x,&y1,&y2); //evident glontul nu poate trece si prin stanga si prin dreapta punctului (0,0)
        if(y1>y2)
            swap(y1,y2);
        if(x>0) //segmentul e in dreapta punctului (0,0)
        {
            nr_dr++;
            dreapta[nr_dr].first=atan2(y1,x);  //unghiul format de OI cu axa Ox (I-inceputul segm)
            dreapta[nr_dr].second=atan2(y2,x); //unghiul format de OS cu axa Ox (S-sfarsitul segm)
        }
        else //segmentul e in stanga punctului (0,0)
        {
            nr_st++;
            stanga[nr_st].first=atan2(y1,-x); //luam valoarea absoluta
            stanga[nr_st].second=atan2(y2,-x);
        }
    }
    //vectorul pair se sorteaza automat crescator dupa componenta first => sortez crescator dupa unghiul format de OI cu axa Ox (I-inceputul segm)
    sort(stanga+1,stanga+nr_st+1);
    sort(dreapta+1,dreapta+nr_dr+1);
    rez=nr_min(stanga,nr_st)+nr_min(dreapta,nr_dr);
    printf("%d",rez);
    return 0;
}