Pagini recente » Cod sursa (job #409971) | Cod sursa (job #607763) | Cod sursa (job #890135) | Cod sursa (job #2106337) | Cod sursa (job #827995)
Cod sursa(job #827995)
#include<fstream>
#include<algorithm>
#define dim 200100
#include<cmath>
const double inf = 1LL<<62;
using namespace std;
ifstream f("rays.in");
ofstream g("rays.out");
int n,i,k,K;
double a,b;
struct cub {
double st,dr;
}
A[dim],B[dim];
int sol(cub A[],int n){
int ans;
ans=1;
double val;
val=-inf;
for(int i=1;i<=n;++i){
if(A[i].st<=val){// daca intalnim un pct de intrare mai mare decat cel mai mare pct de iesire existent adaugam un glont
if(A[i].dr<=val)
val=A[i].dr;
}
else{
++ans;
val=A[i].dr;
}
}
return ans;
}
struct cmp{
inline bool operator () ( const interv &a , const interv &b ){
return a.st < b.st;
}
};
int main () {
f>>n;
double x,y1,y2;
for(i=1;i<=n;++i){
f>>x>>y1>>y2;
if(x>0.0){
a=(double)(y1/x);
b=(double)(y2/x);
if(a>b)
swap(a,b);
A[++k].st=a;
A[k].dr=b;
}
else {
a=-(double)(y1/x);
b=-(double)(y2/x);
if(a>b)
swap(a,b);
B[++K].st=a;
B[K].dr=b;
}
}
//sortam dupa unghi
sort(A+1,A+1+k,cmp());
sort(B+1,B+1+K,cmp());
g<<sol(A,k)+sol(B,K);//aplicam greedy
return 0;
}