Pagini recente » Cod sursa (job #401507) | Cod sursa (job #2315685) | Cod sursa (job #1083427) | Cod sursa (job #2651213) | Cod sursa (job #818862)
Cod sursa(job #818862)
#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;
}
}
return ans;
}
int cmp(cub a,cub b){
if(a.st==b.st)
return a.dr<b.dr;
else
return a.st<b.st;
}
int main () {
f>>n;
int 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;
}