Pagini recente » Cod sursa (job #386083) | Cod sursa (job #2880263) | Cod sursa (job #3208481) | Cod sursa (job #501075) | Cod sursa (job #935546)
Cod sursa(job #935546)
#include<stdio.h>
#include<vector>
#include<algorithm>
#define x first
#define y second
using namespace std;
vector< pair<double , double> > v , b;
inline int cmp(pair<double , double> a , pair<double , double> b)
{
return a.y < b.y;
}
int n , x , y1 , y2;
double r;
int nr;
int main()
{
freopen("rays.in" , "r" , stdin);
freopen("rays.out" , "w" , stdout);
scanf("%d" , &n);
for(int i=1 ; i<=n ; ++i)
{
scanf("%d %d %d" , &x , &y1 , &y2);
if(y1 > y2)
swap(y1 , y2);
///calculez tg de unghiuri
if(x > 0)
v.push_back(make_pair( (double) y1/x , (double) y2/x));
else
b.push_back(make_pair( (double) -1.0000*y1/x , (double) -1.0000*y2/x));
}
sort(v.begin() , v.end() , cmp);
sort(b.begin() , b.end() , cmp);
reverse(b.begin() , b.end());
///acum fac greedy pe unghiuri ca la reactivi
/// pt v
r=b[0].y;
nr=1;
for(int i=1 ; i<b.size() ; ++i)
if(b[i].x > r)
++nr , r=b[i].y;
r=v[0].y;
nr++;
for(int i=1 ; i<v.size() ; ++i)
if(v[i].x > r || v[i].y < r)
++nr , r=v[i].y;
printf("%d\n" , nr);
return 0;
}