Pagini recente » Cod sursa (job #556135) | Cod sursa (job #1111815) | Cod sursa (job #2260687) | Cod sursa (job #1253256) | Cod sursa (job #676975)
Cod sursa(job #676975)
/*
Fiecare dreapta verticala devine interval de tragere
intre 2 unghiuri. => numar minim de valori (pentru unghiuri)
pentru a atinge intervale (problema reactivi de pe infoarena)
pot retine tangenta unghiurilor pentru a evita functiile
trigonometrice (atunci gestionez unghiurile din stanga
si dreapta separat (tragerile sunt semidrepte nu drepte))
alta solutie decat cea oficiala (este suficienta
repartizarea unei drepte la o tragere (nu e nevoie sa se
considere multe trageri))
*/
#include <cstdio>
#include <algorithm>
using namespace std;
struct interval
{
double a,b;
};
const int N_MAX = 200010;
int n,n1,n2;
interval v1[N_MAX], v2[N_MAX];
inline double min(double a, double b)
{
return (a<b)?a:b;
}
interval indreptat(interval x)
{
if (x.a <= x.b)
return x;
return (interval){x.b,x.a};
}
void citeste()
{
int x,y1,y2;
scanf("%d",&n);
for (int i = 1; i <= n; ++i)
{
scanf("%d%d%d",&x,&y1,&y2);
if (x < 0)
v1[++n1] = indreptat(interval{(double)y1/x,(double)y2/x});
else
v2[++n2] = indreptat(interval{(double)y1/x,(double)y2/x});
}
}
bool inceput_crescator(interval x, interval y)
{
return x.a < y.a;
}
int numara_trageri(interval v[], int n)
{
int nrt = 1;
int b_min = v[1].b;
sort(v+1,v+n+1, inceput_crescator);
for (int i = 2; i <= n; ++i)
if (v[i].a < b_min)
b_min = min(b_min,v[i].b);
else
{
++nrt;
b_min = v[i].b;
}
return nrt;
}
int main()
{
int nrt = 0;
freopen("rays.in","r",stdin);
freopen("rays.out","w",stdout);
citeste();
nrt += numara_trageri(v1,n1);
nrt += numara_trageri(v2,n2);
printf("%d",nrt);
return 0;
}