Cod sursa(job #2540518)

Utilizator ardutgamerAndrei Bancila ardutgamer Data 7 februarie 2020 12:07:56
Problema Rays Scor 0
Compilator cpp-64 Status done
Runda irim_eralumis Marime 1.68 kb
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

struct point{
int x,y;
char nr;
double panta()
{
    return (double)y/double(x);
}
};


struct segment{
point A,B;
};

bool cmp(segment a,segment b)
{
    if(a.A.panta() == b.A.panta())
        return a.B.panta() < b.B.panta();
    return a.A.panta() < b.B.panta();
}

vector<segment>v;

bool intersect(double a,double b,double c,double d)
{
    if(((a >= c && a <= d) || (b >= c && b <= d)) || ((c >= a && c <= b) || (d >= a && d <= b)))
        return true;
    return false;
}

int main()
{
    ifstream cin("rays.in");
    ofstream cout("rays.out");
    int n,x,y1,y2;
    cin >> n;
    for(int i = 1 ; i <= n ; i++)
    {
        cin >> x >> y1 >> y2;
        point temp,temp1;
        temp.x = x;
        temp.y = y1;
        temp1.x = x;
        temp1.x = y2;
        temp.nr = temp1.nr = 'A'+i-1;
        segment aux;
        if(temp.panta() > temp1.panta())
            aux = {temp1,temp};
        else
            aux = {temp,temp1};
        v.push_back(aux);
    }
    sort(v.begin(),v.end(),cmp);
    double mi=2000000000;
    double ma=-2000000000;
    int cnt = 2;
    mi = min(mi,v[0].A.panta());
    ma = max(ma,v[0].B.panta());
    for(int i = 1 ; i < v.size() ; i++)
    {
        if(intersect(mi,ma,v[i].B.panta(),v[i].B.panta()))
        {
            mi = min(mi,v[i].A.panta());
            ma = max(ma,v[i].B.panta());
            continue;
        }
        else
        {
            mi = v[i].A.panta();
            ma = v[i].B.panta();
            cnt++;
        }
    }
    cout << cnt << "\n";
    return 0;
}