Pagini recente » Statistici Sonia Maria Manjina (SoniaMaria2008) | Cod sursa (job #530890) | Cod sursa (job #1431458) | Cod sursa (job #2215890) | Cod sursa (job #1514159)
#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;
}