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