Cod sursa(job #1514159)

Utilizator ChristianCunaCuna Cristian ChristianCuna Data 30 octombrie 2015 18:53:28
Problema Rays Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 4.35 kb
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define PI 3.14159265
#define N 200000 // 200_000

int contor = 0;

struct interval{
    float a;
    float b;
};

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

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

typedef struct interval_tree {
    float key1;
    float key2;
    struct interval_tree *left;
    struct interval_tree *middle;
    struct interval_tree *right;
} tree;

tree * new_node(float start, float end){

    tree * newNode=NULL;

    newNode = (tree *)malloc(sizeof(tree));

    newNode->key1 = start;//intrv.a;
    newNode->key2 = end;//intrv.b;
    newNode->left = NULL;
    newNode->right = NULL;
    newNode->middle = NULL;

    return newNode;

}

tree * insert(tree * root, struct interval intrv){
    if(root == NULL)
        return new_node(intrv.a, intrv.b);

    if(intrv.b < root->key1)
        root->left = insert(root->left, intrv);
    else
        if(intrv.a > root->key2)
            root->right = insert(root->right, intrv);
        else
            root->middle = insert(root->middle, intrv);

    return root;
}

void swap(int *a, int *b){
    int 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;
}

void rays(tree * root){
    /** function: print tree in Left-root-Right order
        parameter: root
        return: none
    */
    if(root == NULL){
        printf("root is empty!\n");
        return;
    }
    /** Print left.*/
    if(root->left != NULL){
        contor++;
        rays(root->left);
    }
    /** Print root.*/
    if(root->middle != NULL)
        rays(root->middle);

    /** Print right.*/
    if(root->right != NULL){
        contor++;
        rays(root->right);
    }
}

void inorder(tree * root){
    /** function: print tree in Left-root-Right order
        parameter: root
        return: none
    */
    if(root == NULL){
        printf("root is empty!\n");
        return;
    }
    /** Print left.*/
    if(root->left != NULL)
        inorder(root->left);

    /** Print root.*/
    printf("\nstart: %f \t end: %f ", root->key1, root->key2);
    if(root->middle != NULL)
        inorder(root->middle);

    /** Print right.*/
    if(root->right != NULL)
        inorder(root->right);
}

int main(){

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

    struct segment seg;

    struct interval angle;

    int seg_nr;

    tree *left=NULL, *right=NULL;

    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){
            angle = angles(seg);
            left = insert(left, angle);
        }
        else{
            angle = angles(seg);
            right = insert(right, angle);
        }
    }
/*
    inorder(left);
    inorder(right);*/

    if(left != NULL)
        contor++;
    if(right != NULL)
        contor++;

    rays(left);
    rays(right);

    printf("\n%d\n", contor);
    return 0;
}