Pagini recente » Cod sursa (job #118370) | Cod sursa (job #1511204) | Cod sursa (job #1853162) | Cod sursa (job #1498949) | Cod sursa (job #2018579)
#include<bits/stdc++.h>
#define maxN 200005
#define dim 1000000
using namespace std;
typedef struct tip
{
double slope;
int index,type;
};
bool cmp(tip a,tip b)
{
if(a.slope==b.slope) return a.index<b.index;
return a.slope<b.slope;
}
bool inStack[maxN];
int sol,vf;
tip st[maxN];
char buff[dim+5];
int pos=0;
vector<tip> events1,events2;
inline void read(int &nr)
{
nr=0;
while(buff[pos]<'0' || buff[pos]>'9')
{
pos++;
if(pos==dim)
{
pos=0;
fread(buff,1,dim,stdin);
}
}
while(buff[pos]>='0' && buff[pos]<='9')
{
nr=nr*10+buff[pos]-'0';
pos++;
if(pos==dim)
{
pos=0;
fread(buff,1,dim,stdin);
}
}
}
inline void Solve(vector<tip> events)
{
vf=0;
memset(inStack,0,sizeof(inStack));
for(vector<tip>::iterator it=events.begin();it!=events.end();it++)
{
if(it->type==0)
{
//st.push(*it);
st[++vf]=*it;
inStack[it->index]=1;
}
else
{
if(!inStack[it->index]) continue;
sol++;
while(vf)
{
int x=st[vf].index;
vf--;
inStack[x]=0;
// if(x==it->index) break;
}
}
}
}
int n,x,y,z;
int main()
{
freopen("rays.in","r",stdin);
freopen("rays.out","w",stdout);
fread(buff,1,dim,stdin);
read(n);
for(int i=1;i<=n;i++)
{
// scanf("%d%d%d",&x,&y,&z);
read(x);
read(y);
read(z);
if(y>z) swap(y,z);
if(x>0)
{
events1.push_back({(1.0*y)/x,i,0});
events1.push_back({(1.0*z)/x,i,1});
}
else
{
events2.push_back({(-1.0*y)/x,i,0});
events2.push_back({(-1.0*z)/x,i,1});
}
}
sort(events1.begin(),events1.end(),cmp);
sort(events2.begin(),events2.end(),cmp);
Solve(events1);
Solve(events2);
printf("%d\n",sol);
return 0;
}