Cod sursa(job #1517723)

Utilizator ChristianCunaCuna Cristian ChristianCuna Data 4 noiembrie 2015 18:51:49
Problema Rays Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.71 kb
#include <fstream>
#include <algorithm>
#include <stdlib.h>
#include <math.h>

const int PI=3.14159265;
const int N=200000; // 200_000

using namespace std;

ifstream input("rays.in");
ofstream output("rays.out");

struct interval{
    float a;
    float b;
};

struct segment{
    int x;
    int y1;
    int y2;
};

struct triangle{
    float a;
    float b;
    float c;
};

void swap(int *a, int *b){
    int aux;
    aux = *a;
    *a = *b;
    *b = aux;
}

interval angles(struct segment seg){
    interval intrv;

    triangle tr;
    double val = 180 / PI;
    float cosA;
    /************ Calculate interval's upper limit ************/
    /** Set a */

    if(seg.y1 > seg.y2)
        swap(&seg.y1, &seg.y2);

    if(seg.x >= 0)
        tr.a = seg.x;
    else
        tr.a = -seg.x;
    /** Set b */

    if(seg.y2 != 0){
        if(seg.y2 > 0)
            tr.b = seg.y2;
        else
            tr.b = -seg.y2;
        /** Calculate c */
        tr.c = sqrt(pow(tr.a, 2) + pow(tr.b, 2));
        /** Calculate cos(c) with the Cosine Rule*/
        cosA = (pow(tr.a, 2) - pow(tr.b, 2) - pow(tr.c, 2)) / (-1 * 2 * tr.b * tr.c);
        if(seg.y2 > 0)
            intrv.b =  180 - val * acos(cosA);
        else
            intrv.b =  180 - val * acos(cosA);
    }
    else
        intrv.b = 90;
    /************ Calculate interval's lower limit ************/

    /** Set b */
    if(seg.y1 != 0){
        if(seg.y1 > 0)
            tr.b = seg.y1;
        else
            tr.b = -seg.y1;
        /** Calculate c */
        tr.c = sqrt(pow(tr.a, 2) + pow(tr.b, 2));
        /** Calculate cos(c) with the Cosine Rule*/
        cosA = (pow(tr.a, 2) - pow(tr.b, 2) - pow(tr.c, 2)) / (-1 * 2 * tr.b * tr.c);
        if(seg.y1 > 0)
            intrv.a = 180 - val * acos(cosA);
        else
            intrv.a = val * acos(cosA);
    }
    else
        intrv.a = 90;

    return intrv;
}

bool compare(interval int1, interval int2){
    if(int1.a != int2.a)
        return int1.a < int2.a;
    return int1.b < int2.b;
}

int main(){

    segment seg;

    interval left_arr[N], right_arr[N];

    int seg_nr, left=0, right=0, right_solution=0, left_solution=0;

    input>>seg_nr;

    for(int i = 0; i < seg_nr; ++i){

        input>>seg.x;
        input>>seg.y1;
        input>>seg.y2;

        if(seg.x > 0)
            right_arr[right++] = angles(seg);
        else
            left_arr[left++] = angles(seg);

    }
/*
    output<<"Right:"<<endl;

    for(int i = 0; i < right; ++i){
        output<<right_arr[i].a<<" "<<right_arr[i].b<<endl;
    }
*/
    sort(right_arr, right_arr + right, compare);
/*
    output<<endl<<"Right:"<<endl;

    for(int i = 0; i < right; ++i){
        output<<right_arr[i].a<<" "<<right_arr[i].b<<endl;
    }

    output<<endl<<"Left:"<<endl;

    for(int i = 0; i < left; ++i){
        output<<left_arr[i].a<<" "<<left_arr[i].b<<endl;
    }*/

    sort(left_arr, left_arr + left, compare);
/*
    output<<endl<<"Left:"<<endl;

    for(int i = 0; i < left; ++i){
        output<<left_arr[i].a<<" "<<left_arr[i].b<<endl;
    }*/

    float min_ending;
    min_ending = right_arr[0].b;

    for(int i = 0; i < right; ++i){
        if(right_arr[i].a > min_ending){
            ++right_solution;
            min_ending = right_arr[i].b;
        }
        else if(right_arr[i].b < min_ending)
            min_ending = right_arr[i].b;
    }

    ++right_solution;
    min_ending = left_arr[0].b;

    for(int i = 0; i < left; ++i){
        if(left_arr[i].a > min_ending){
            ++left_solution;
            min_ending = left_arr[i].b;
        }
        else if(left_arr[i].b < min_ending)
            min_ending = left_arr[i].b;
    }
    ++left_solution;

    output<<left_solution + right_solution;

    input.close();
    output.close();

    return 0;
}