Pagini recente » Cod sursa (job #2298690) | Cod sursa (job #3285352) | Cod sursa (job #28136) | Cod sursa (job #1071794) | Cod sursa (job #818883)
Cod sursa(job #818883)
#include<fstream>
#include<algorithm>
#define dim 200100
#include<cmath>
using namespace std;
ifstream f("rays.in");
ofstream g("rays.out");
int n,i,k,K;
double a,b;
struct cub {
long double st,dr;
}
A[dim],B[dim];
int sol(cub A[],int n){
int ans;
long double val;
ans=1;
val=A[1].dr;
for(int i=2;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
ans++;
val=A[i].dr;
}
else
if(val>A[i].dr)
val=A[i].dr;
}
return ans;
}
int cmp(cub a,cub b){
return a.st<b.st;
}
int main () {
f>>n;
long double x,y1,y2;
for(i=1;i<=n;++i){
f>>x>>y1>>y2;
if(x>0.0){
a=atan2(y1,x);
b=atan2(y2,x);
if(a>b)
swap(a,b);
A[++k].st=a;
A[k].dr=b;
}
else {
a=atan2(y1,-x);
b=atan2(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;
}