Cod sursa(job #115654)

Utilizator ZeusCatalin Tiseanu Zeus Data 16 decembrie 2007 19:13:20
Problema Rays Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.69 kb

#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;

#define node pair< pair<int,int>, pair<int,int> >

#define MN 201222

int N, mx[MN], my1[MN], my2[MN], NE, was[MN];
node ev[2*MN];

bool cmp( node e1, node e2 )
{
    double val = atan2( 1.0 * e1.first.second, e1.first.first ) -
               atan2( 1.0 * e2.first.second, e2.first.first ); 
     
    if( abs(val) > 1e-9 )
        return val <= 0.0;
        
    return e1.second.first < e2.second.first;
     
} 

int main()
{
    freopen("rays.in", "r", stdin);
    freopen("rays.out", "w", stdout);
    
    scanf("%d", &N);
    for( int i = 1; i <= N; ++i )
    {
         scanf("%d %d %d", mx + i, my1 + i, my2 + i );
         
         node e1 = make_pair( make_pair(mx[i],my1[i]), make_pair(-1,i) );
         node e2 = make_pair( make_pair(mx[i],my2[i]), make_pair( 1,i) );
    
         if( cmp(e2,e1) )
             e1.second.first = 1, 
             e2.second.first = -1;
         
         ev[NE++] = e1, ev[NE++] = e2;
    }
    
    sort( ev, ev + NE, cmp );
     
    int last = NE + 1, ret = 0; 
     
//    for( int i = 0; i < NE; ++i )
//         printf("%d,%d\n", ev[i].first.first, ev[i].first.second ); 
     
    for( int i = 0; i < NE; ++i )
    {
         pair<int,int> state = ev[i].second;
         
//         printf("-> %d %d\n", state.second, state.first );
         
         if( state.first == -1 )
         {
             was[ state.second ] = i;
         }      
         else
         {
             if( was[ state.second ] >= last );
             else{ ++ret, last = i; }
         }
    } 
    
    printf("%d\n", ret);
     
    return 0;
}