Pagini recente » Cod sursa (job #1397162) | Cod sursa (job #2537448) | Cod sursa (job #1254068) | Cod sursa (job #2682393) | Cod sursa (job #349327)
Cod sursa(job #349327)
//100 puncte
#include<math.h>
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
#define pb push_back
#define mkp make_pair
#define ld long double
#define nm 200005
int sx[nm],sy1[nm],sy2[nm],in[nm],care[nm];
vector<pair<double,pair<int,int> > > maimuta;
int main()
{
int x,y1,y2,i,j,ans=0,n;
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);
sx[i]=x;
if(y1<y2)
{
sy1[i]=y1;
sy2[i]=y2;
}
else
{
sy1[i]=y2;
sy2[i]=y1;
}
}
//rezolv partea dreapta
for(i=1;i<=n;i++)
if(sx[i]>0)
{
double val_sin=(ld)sx[i]/(ld)sqrt((ld)sx[i]*sx[i]+(ld)sy1[i]*sy1[i]);
val_sin=1-val_sin;
if(sy1[i]<0) val_sin=-val_sin;
maimuta.pb(mkp(val_sin,mkp(0,i)));
val_sin=(ld)sx[i]/(ld)sqrt((ld)sx[i]*sx[i]+(ld)sy2[i]*sy2[i]);
val_sin=1-val_sin;
if(sy2[i]<0) val_sin=-val_sin;
maimuta.pb(mkp(val_sin,mkp(1,i)));
}
sort(maimuta.begin(),maimuta.end());
//afisare
/*
for(i=0;i<maimuta.size();i++)
{
printf("%lf ",maimuta[i].first);
printf("%d ",maimuta[i].second.first);
printf("%d",maimuta[i].second.second);
printf("\n");
}
*/
int dim=0;
for(i=0;i<maimuta.size();i++)
{
int ee=maimuta[i].second.first;
int segm=maimuta[i].second.second;
//daca e sf de segment care e deja scos
//il ignor
if(ee&&!in[segm]) continue;
//daca e sf de segment care e inauntru
//actualizez solutia si sparg coada
if(ee&&in[segm])
{
ans++;
for(j=1;j<=dim;j++)
in[care[j]]=0;
dim=0;
continue;
}
//daca e inceput de segm il bag in coada
care[++dim]=segm;
in[segm]=1;
}
//rezolv partea stanga
//schimb maimuta
maimuta.clear();
for(i=1;i<=n;i++)
if(sx[i]<0)
{
double val_sin=(ld)-sx[i]/(ld)sqrt((ld)sx[i]*sx[i]+(ld)sy1[i]*sy1[i]);
val_sin=1-val_sin;
if(sy1[i]<0) val_sin=-val_sin;
maimuta.pb(mkp(val_sin,mkp(0,i)));
val_sin=(ld)-sx[i]/(ld)sqrt((ld)sx[i]*sx[i]+(ld)sy2[i]*sy2[i]);
val_sin=1-val_sin;
if(sy2[i]<0) val_sin=-val_sin;
maimuta.pb(mkp(val_sin,mkp(1,i)));
}
sort(maimuta.begin(),maimuta.end());
dim=0;
for(i=0;i<maimuta.size();i++)
{
int ee=maimuta[i].second.first;
int segm=maimuta[i].second.second;
//daca e sf de segment care e deja scos
//il ignor
if(ee&&!in[segm]) continue;
//daca e sf de segment care e inauntru
//actualizez solutia si sparg coada
if(ee&&in[segm])
{
ans++;
for(j=1;j<=dim;j++)
in[care[j]]=0;
dim=0;
continue;
}
//daca e inceput de segm il bag in coada
care[++dim]=segm;
in[segm]=1;
}
printf("%d",ans);
return 0;
}