Pagini recente » Cod sursa (job #1524796) | Cod sursa (job #2937421) | Cod sursa (job #2766557) | Cod sursa (job #2369182) | Cod sursa (job #923434)
Cod sursa(job #923434)
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cstring>
#define eps 1.e-9;
using namespace std;
int x,y1,y2,rays,i,n;
struct tip1
{
int i;
double p;
};
tip1 t;
vector <tip1> v;
vector <tip1> v1;
int n1,n2;
bool cmp(const tip1 &a,const tip1 &b)
{
return a.p-b.p<-eps;
}
int viz[200100],p[200100],rays2;
int main()
{
freopen("rays.in","r",stdin);
freopen("rays.out","w",stdout);
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d%d%d",&x,&y1,&y2);
if(x>0)
{
n1++;
t.p=(double)y1/x;
t.i=i;
v.push_back(t);
t.p=(double)y2/x;
t.i=i;
v.push_back(t);
}
if(x<0)
{
n2++;
t.p=(double)y1/x;
t.i=i;
v1.push_back(t);
t.p=(double)y2/x;
t.i=i;
v1.push_back(t);
}
}
sort(v.begin(),v.end(),cmp);
sort(v1.begin(),v1.end(),cmp);
rays=1;
for(i=0;i<2*n1;i++)
{
t=v[i];
if(viz[t.i]==0)
{
viz[t.i]=rays;
}
else
{
if(p[viz[t.i]]==1)
{
continue;
}
else
{
rays++;
p[viz[t.i]]=1;
}
}
}
memset(viz,0,2*n1);
memset(p,0,2*n1);
rays2=1;
for(i=0;i<2*n2;i++)
{
t=v1[i];
if(viz[t.i]==0)
{
viz[t.i]=rays;
}
else
{
if(p[viz[t.i]]==1)
{
continue;
}
else
{
rays2++;
p[viz[t.i]]=1;
}
}
}
printf("%d",rays-1+rays2-1);
return 0;
}