Pagini recente » Cod sursa (job #1362531) | Rating Barila Matei (Matei_Barila) | Cod sursa (job #1455239) | Cod sursa (job #348732) | Cod sursa (job #1339626)
//#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#define nmax 400001
using namespace std;
FILE *f=fopen("rays.in","r"),*g=fopen("rays.out","w");
struct punct{
int x,y;
int tip,id;/*tip 0=inceput, tip 1=sfarsit*/
}poz[nmax],neg[nmax];
int lgpoz,lgneg,nr,viz[nmax/2+1];
int criteriu(punct a, punct b)
{
double ua,ub;
//cout<<a.x<<" "<<a.y<<"-"<<b.x<<" "<<b.y<<"\n";
ua=(double)a.y/a.x; ub=(double)b.y/b.x;
//cout<<ua<<" "<<ub<<"\n";
if(ua<ub)
return 1;
return 0;
}
int main()
{
int i,j,n,x,maxid=0; queue <punct> q; punct aux;
fscanf(f,"%d",&n);
for(i=1;i<=n;i++)
{
fscanf(f,"%d",&x);
if(x<0)
{
x=-x;
fscanf(f,"%d %d",&neg[++lgneg].y,&neg[++lgneg].y);
neg[lgneg-1].x=x; neg[lgneg].x=x;
neg[lgneg-1].id=neg[lgneg].id=i;
if(neg[lgneg-1].y<neg[lgneg].y)
{
neg[lgneg-1].tip=0;
neg[lgneg].tip=1;
}
else
{
neg[lgneg-1].tip=1;
neg[lgneg].tip=0;
}
}
else
{
fscanf(f,"%d %d",&poz[++lgpoz].y,&poz[++lgpoz].y);
poz[lgpoz-1].x=poz[lgpoz].x=x;
poz[lgpoz-1].id=poz[lgpoz].id=i;
if(poz[lgpoz-1].y<poz[lgpoz].y)
{
poz[lgpoz-1].tip=0;
poz[lgpoz].tip=1;
}
else
{
poz[lgpoz-1].tip=1;
poz[lgpoz].tip=0;
}
}
}
sort(neg+1,neg+lgneg+1,criteriu);
sort(poz+1,poz+lgpoz+1,criteriu);
for(i=1;i<=lgneg;i++)
if(!viz[neg[i].id])
{
q.push(neg[i]);
if(neg[i].tip==1)
{
nr++;
while(!q.empty())
{
aux=q.front();
q.pop();
viz[aux.id]=1;
if(aux.id>maxid) maxid=aux.id;
}
}
}
for(i=1;i<=maxid;i++)
viz[i]=0;
for(i=1;i<=lgpoz;i++)
if(!viz[poz[i].id])
{
q.push(poz[i]);
if(poz[i].tip==1)
{
nr++;
while(!q.empty())
{
aux=q.front();
q.pop();
viz[aux.id]=1;
}
}
}
fprintf(g,"%d",nr);
fclose(f);
fclose(g);
return 0;
}