Cod sursa(job #349327)

Utilizator perticas_catalinperticas catalin perticas_catalin Data 19 septembrie 2009 01:35:17
Problema Rays Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.33 kb
//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;
}