Pagini recente » Cod sursa (job #2479990) | Cod sursa (job #2225296) | Cod sursa (job #1947053) | Cod sursa (job #1286532) | Cod sursa (job #1519557)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("rays.in");
ofstream fout("rays.out");
int n,n1,n2,i,viz[200001],NR,ultim1,ultim2;
double x,y1,y2;
struct date
{
int ord;
double sus,jos;
}v1[200001],v2[200001],v3[200001],v4[200001];
int cmp(date A,date B)
{
if(A.sus==B.sus)
return A.jos<B.jos;
else
return A.sus<B.sus;
}
int cmp2(date A,date B)
{
if(A.jos==B.jos)
return A.sus<B.sus;
else
return A.jos<B.jos;
}
int main()
{
fin>>n;
for(i=1;i<=n;i++)
{
fin>>x>>y1>>y2;
if(y1>y2)
swap(y1,y2);
if(x>0)
{
n1++;
v1[n1].ord=i;
v2[n1].ord=i;
v1[n1].jos=y1/x;
v1[n1].sus=y2/x;
v2[n1].jos=v1[n1].jos;
v2[n1].sus=v1[n1].sus;
}
else
{
n2++;
x=-x;
v3[n2].ord=i;
v4[n2].ord=i;
v3[n2].jos=y1/x;
v3[n2].sus=y2/x;
v4[n2].jos=v3[n2].jos;
v4[n2].sus=v3[n2].sus;
}
}
sort(v1+1,v1+n1+1,cmp);
sort(v2+1,v2+n1+1,cmp2);
sort(v3+1,v3+n2+1,cmp);
sort(v4+1,v4+n2+1,cmp2);
ultim1=1;
NR=0;
for(i=1;i<=n1;i++)
{
if( viz[v1[i].ord] == 0 )
{
viz[v1[i].ord] = 1;
NR++;
while( v2[ultim1].jos <= v1[i].sus && ultim1 <= n1)
{
viz[v2[ultim1].ord] = 1;
ultim1++;
}
}
}
ultim2=1;
for(i=1;i<=n2;i++)
{
if( viz[v3[i].ord] == 0 )
{
viz[v3[i].ord] = 1;
NR++;
while( v4[ultim2].jos <= v3[i].sus && ultim2 <= n2)
{
viz[v4[ultim2].ord] = 1;
ultim2++;
}
}
}
fout<<NR;
return 0;
}