Cod sursa(job #1514807)

Utilizator ChristianCunaCuna Cristian ChristianCuna Data 31 octombrie 2015 17:07:36
Problema Rays Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 3.64 kb
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define PI 3.14159265
#define N 200000 // 200_000

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;
}

void swap_i(struct interval *a, struct interval *b){
    struct interval aux;
    aux = *a;
    *a = *b;
    *b = aux;
}

struct interval angles(struct segment seg){
    struct interval intrv;

    struct 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;
}

int partition (struct interval arr[], int l, int h){
    int x = arr[h].a;
    int i = (l - 1);

    for (int j = l; j <= h- 1; j++)
    {
        if (arr[j].a <= x)
        {
            i++;
            swap_i(&arr[i], &arr[j]);
        }
    }
    swap_i (&arr[i + 1], &arr[h]);
    return (i + 1);
}
/* A[] --> Array to be sorted, l  --> Starting index, h  --> Ending index */
void quickSort(struct interval A[], int l, int h){
    if (l < h)
    {
        int p = partition(A, l, h); /* Partitioning index */
        quickSort(A, l, p - 1);
        quickSort(A, p + 1, h);
    }
}

void print(struct interval *array, int n){
    for(int i = 0; i < n; i++)
        printf("%f %f\n", array[i].a, array[i].b);
}

int rays(struct interval *array, int size){
    if(size == 0)
        return 0;

    int count=0;

    float current_end=array[0].b;

    for(int i = 1; i < size; i++)
        if(array[i].a > current_end){
            count++;
            current_end = array[i].b;
        }

    return ++count;
}

int main(){

    freopen("rays.in", "r", stdin);
    freopen("rays.out", "w", stdout);

    struct segment seg;

    struct interval l_array[N], r_array[N];

    int seg_nr, left_size=0, right_size=0;

    scanf("%d", &seg_nr);

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

        scanf("%d", &seg.x);
        scanf("%d", &seg.y1);
        scanf("%d", &seg.y2);

        if(seg.x < 0)
            l_array[left_size++] = angles(seg);
        else
            r_array[right_size++] = angles(seg);

    }

    quickSort(l_array, 0, left_size-1);
    quickSort(r_array, 0, right_size-1);

    printf("Left\n");
    print(l_array, left_size);
    printf("\nRight\n");
    print(r_array, right_size);

    printf("%d", rays(l_array, left_size) + rays(r_array, right_size));

    return 0;
}