Cod sursa(job #2540447)

Utilizator gavra_bogdanBogdan Gavra gavra_bogdan Data 7 februarie 2020 10:16:57
Problema Rays Scor 100
Compilator cpp-64 Status done
Runda irim_eralumis Marime 1.71 kb
#include <bits/stdc++.h>
#define pi pair<int,int>
#define ppi pair<int,pi>
#define x first
#define y second
#define PI 3.14159265
using namespace std;

const int nmax=2e5+5;

vector<ppi>v;
vector<ppi>aux;
bool viz[nmax];
pi in[nmax];

pair<double,double> trans(ppi z)
{
    pi a={z.x,z.y.x};
    pi b={z.x,z.y.y};
    if(z.y.x<z.y.y)
        swap(a,b);
    double ua=atan((double)a.x/(double)a.y)*180.0/PI;
    double ub=atan((double)b.x/(double)b.y)*180.0/PI;
    if(ua<0)
        ua=180.0-fabs(ua);
    if(ub<0)
        ub=180.0-fabs(ub);
    return {ua,ub};
}

int solve(vector<ppi>&v)
{
    queue<int>q;
    vector<pair<double,pi>>c;
    memset(viz,0,sizeof(viz));
    int k=0;
    for(auto zx:v)
    {
        auto z=trans(zx);
        in[++k]=z;
        c.push_back({z.x,{0,k}});
        c.push_back({z.y,{1,k}});
    }
    int ans=0;
    sort(c.begin(),c.end());
    for(auto z:c)
        if(viz[z.y.y]==0)
            if(z.y.x==0)
                q.push(z.y.y);
            else
            {
                while(!q.empty())
                    {
                        viz[q.front()]=1;
                        q.pop();
                    }
                ans++;
            }
    if(!q.empty())
        ans++;
    return ans;
}

int main()
{
    ifstream cin("rays.in");
    ofstream cout("rays.out");
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,a,b,c;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a>>b>>c;
        if(a>0)
            v.push_back({a,{b,c}});
        else
            aux.push_back({-a,{b,c}});
    }
    int sol1=solve(v);
    int sol2=solve(aux);
    cout<<sol1+sol2;
    return 0;
}