Pagini recente » Cod sursa (job #2655416) | Cod sursa (job #218052) | Cod sursa (job #1140254) | Cod sursa (job #1328300) | Cod sursa (job #347223)
Cod sursa(job #347223)
#include<fstream>
#include<algorithm>
using namespace std;
const char iname[]="rays.in";
const char oname[]="rays.out";
const int maxn=400005;
ifstream f(iname);
ofstream g(oname);
struct unghi
{
int x;
int y;
bool t;
int l;
} a[maxn],b[maxn];
bool operator<(const unghi& a,const unghi& b)
{
return (long long)a.x*(long long)b.y<=(long long)a.y*(long long)b.x;
}
int i,j,n,k,x,y1,y2,t,r,mark[maxn],coada[maxn],poz[maxn],size;
bool fcomp(int x,int y)
{
return a[x]<a[y];
}
bool fcomp2(int x,int y)
{
return b[x]<b[y];
}
int main()
{
f>>n;
for(i=1;i<=n;++i)
{
f>>x>>y1>>y2;
if(x>0)
a[++k].x=min(y1,y2),a[k].y=x,a[k].t=true,
a[++k].x=max(y1,y2),a[k].y=x,a[k].t=false,
a[k].l=k-1;
else
b[++t].x=min(y1,y2),b[t].y=-x,b[t].t=true,
b[++t].x=max(y1,y2),b[t].y=-x,b[t].t=false,
b[t].l=t-1;
}
for(i=1;i<=k;++i)
poz[i]=i;
sort(poz+1,poz+k+1,fcomp);
for(i=1;i<=k;++i)
if(a[poz[i]].t==true)
coada[++size]=poz[i];
else
if(mark[a[poz[i]].l]==0)
{
for(;size;--size)
mark[coada[size]]=1,coada[size]=0;
++r;
}
for(i=1;i<=t;++i)
poz[i]=i,mark[i]=0;
sort(poz+1,poz+t+1,fcomp2);
for(i=1;i<=t;++i)
if(b[poz[i]].t==true)
coada[++size]=poz[i];
else
if(mark[b[poz[i]].l]==0)
{
for(;size;--size)
mark[coada[size]]=1,coada[size]=0;
++r;
}
g<<r<<"\n";
f.close();
g.close();
return 0;
}