Pagini recente » Cod sursa (job #1030586) | Cod sursa (job #1800399) | Cod sursa (job #2687865) | Cod sursa (job #2437643) | Cod sursa (job #818871)
Cod sursa(job #818871)
#include<fstream>
#include<algorithm>
#define dim 200007
#include<cmath>
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;
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;
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;
}