Pagini recente » Cod sursa (job #1766247) | Cod sursa (job #241712) | Cod sursa (job #1934548) | Cod sursa (job #1035893) | Cod sursa (job #2076188)
#include<cstdio>
#include<stack>
#include<algorithm>
#include<cmath>
using namespace std;
struct punct
{
int x,y,nr;
bool stare;
};
stack<int>st;
const double eps=1.e-14;
bool cmp1(punct a,punct b)
{
if(fabs(((double)a.y/(double)a.x)-((double)b.y/(double)b.x))<eps)
return a.stare>b.stare;
else
return ((double)a.y/(double)a.x)-((double)b.y/(double)b.x)<=-eps;
}
bool cmp2(punct a,punct b)
{
if(fabs(((double)a.y/(double)a.x)-((double)b.y/(double)b.x))<eps)
return a.stare>b.stare;
else
return ((double)a.y/(double)a.x)-((double)b.y/(double)b.x)>=eps;
}
punct v1[200001],v2[200001];
bool f1[200001],f2[200001];
int main()
{
freopen("rays.in","r",stdin);
freopen("rays.out","w",stdout);
int n,i,x,y1,y2,nr1=0,nr2=0;
scanf("%d",&n);
for(i=1;i<=n;++i)
{
scanf("%d%d%d",&x,&y1,&y2);
if(x>0)
{
nr1++;
v1[(2*nr1)-1].x=v1[2*nr1].x=x;
v1[(2*nr1)-1].y=y1;
v1[2*nr1].y=y2;
v1[(2*nr1)-1].nr=v1[2*nr1].nr=i;
if(y1<=y2)
v1[(2*nr1)-1].stare=1;
else
v1[2*nr1].stare=1;
}
else
{
nr2++;
v2[(2*nr2)-1].x=v2[2*nr2].x=x;
v2[(2*nr2)-1].y=y1;
v2[2*nr2].y=y2;
v2[(2*nr2)-1].nr=v2[2*nr2].nr=i;
if(y1<=y2)
v2[(2*nr2)-1].stare=1;
else
v2[2*nr2].stare=1;
}
}
sort(v1+1,v1+(2*nr1)+1,cmp1);
sort(v2+1,v2+(2*nr2)+1,cmp2);
int sol=0;
for(i=1;i<=2*nr1;++i)
{
if(v1[i].stare)
st.push(v1[i].nr);
else
{
if(!f1[v1[i].nr])
{
sol++;
while(!st.empty())
{
f1[st.top()]=1;
st.pop();
}
}
}
}
for(i=1;i<=2*nr2;++i)
{
if(v2[i].stare)
st.push(v2[i].nr);
else
{
if(!f2[v2[i].nr])
{
sol++;
while(!st.empty())
{
f2[st.top()]=1;
st.pop();
}
}
}
}
printf("%d\n",sol);
return 0;
}