Pagini recente » Cod sursa (job #2201923) | Cod sursa (job #1078610) | Cod sursa (job #926609) | Cod sursa (job #1089298) | Cod sursa (job #1517723)
#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;
};
struct triangle{
float a;
float b;
float c;
};
void swap(int *a, int *b){
int aux;
aux = *a;
*a = *b;
*b = aux;
}
interval angles(struct segment seg){
interval intrv;
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;
}
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++] = angles(seg);
else
left_arr[left++] = angles(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;
}
++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;
}
++left_solution;
output<<left_solution + right_solution;
input.close();
output.close();
return 0;
}