Pagini recente » Cod sursa (job #1275392) | Cod sursa (job #2684794) | Cod sursa (job #2572830) | Cod sursa (job #2263884) | Cod sursa (job #1519463)
#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;
};
float slope(int point_x, int point_y){
return float(point_y) / float(point_x);
}
interval calculate_interval(segment seg){
interval temp;
temp.a = slope(seg.x, seg.y1);
temp.b = slope(seg.x, seg.y2);
if(temp.b < temp.a)
swap(temp.b, temp.a);
return temp;
}
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++] = calculate_interval(seg);
else
left_arr[left++] = calculate_interval(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;
}
if(right)
++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;
}
if(left)
++left_solution;
//output<<"\nLeft:"<<left_solution;
//output<<"\nRight:"<<right_solution<<endl;
output<<left_solution + right_solution;
input.close();
output.close();
return 0;
}