Cod sursa(job #1519463)

Utilizator ChristianCunaCuna Cristian ChristianCuna Data 7 noiembrie 2015 13:06:57
Problema Rays Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.6 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;
};

float slope(int point_x, int point_y){
    return float(point_y) / float(point_x);
}

interval calculate_interval(segment seg){

    interval temp;

    temp.a = slope(seg.x, seg.y1);
    temp.b = slope(seg.x, seg.y2);

    if(temp.b < temp.a)
        swap(temp.b, temp.a);

    return temp;

}

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++] = calculate_interval(seg);
        else
            left_arr[left++] = calculate_interval(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;
    }

    if(right)
        ++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;
    }
    if(left)
        ++left_solution;

    //output<<"\nLeft:"<<left_solution;
    //output<<"\nRight:"<<right_solution<<endl;
    output<<left_solution + right_solution;

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

    return 0;
}