Cod sursa(job #2076466)

Utilizator cyg_vladioanBirsan Vlad cyg_vladioan Data 26 noiembrie 2017 17:15:29
Problema Rays Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.29 kb
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
const double eps = 1.e-14;
const double PI = 2.0 * acos(0);
struct rays
{
    double u1 , u2;
};
vector <rays> l , r;
double cmp(rays a , rays b)
{
    return a.u1 < b.u1;
}
int main()
{
    freopen("rays.in" , "r" , stdin);
    freopen("rays.out" , "w" , stdout);
    int n , x , y1 , y2 , i , sol , nr;
    double st , dr;
    scanf("%d" , &n);
    rays temp;
    for(i = 1 ; i <= n ; i ++)
    {
        scanf("%d%d%d" , &x , &y1 , &y2);
        if(y2 < y1)
        {
            int aux = y1;
            y1 = y2;
            y2 = aux;
        }
        temp.u1 = atan2(y1 , x);
        temp.u2 = atan2(y2 , x);
        if(temp.u1 <= -eps)
            temp.u1 = temp.u1 + 2 * PI;
        if(temp.u2 <= -eps)
            temp.u2 = temp.u2 + 2 * PI;
        if(x >= 0)
        {
            if(y1 <= 0)
                temp.u1 = temp.u1 - 1.5 * PI;
            else
                temp.u1 = temp.u1 + 0.5 * PI;
            if(y2 <= 0)
                temp.u2 = temp.u2 - 1.5 * PI;
            else
                temp.u2 = temp.u2 + 0.5 * PI;
            r.push_back(temp);
        }
        else
        {
            temp.u1 = 1.5 * PI - temp.u1;
            temp.u2 = 1.5 * PI - temp.u2;
            l.push_back(temp);
        }
    }
    sort(r.begin() , r.end() , cmp);
    sort(l.begin() , l.end() , cmp);
    sol = n;
    st = r[0].u1;
    dr = r[0].u2;
    nr = 1;
    for(i = 1 ; i < r.size() ; i ++)
        if(dr - r[i].u1 > -eps)
        {
            st = max(r[i].u1 , st);
            dr = min(r[i].u2 , dr);
            nr ++;
        }
        else
        {
            st = r[i].u1;
            dr = r[i].u2;
            sol = sol - nr + 1;
            nr = 1;
        }
    sol = sol - nr + 1;
    st = l[0].u1;
    dr = l[0].u2;
    nr = 1;
    for(i = 1 ; i < l.size() ; i ++)
        if(dr - l[i].u1 > -eps)
        {
            st = max(l[i].u1 , st);
            dr = min(l[i].u2 , dr);
            nr ++;
        }
        else
        {
            st = l[i].u1;
            dr = l[i].u2;
            sol = sol - nr + 1;
            nr = 1;
        }
    sol = sol - nr + 1;
    printf("%d\n" , sol);
    return 0;
}