Cod sursa(job #329006)

Utilizator tamas_iuliaTamas Iulia tamas_iulia Data 4 iulie 2009 13:01:46
Problema Rays Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 kb
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define x first.first
#define y first.second
#define tip second.first
#define nr second.second
#define LL long long
typedef pair < pair<int,int>, pair<bool,int> > punct;
#define mp make_pair
#define MP(a,b,c,d) mp(mp(a,b),mp(c,d))
#define Nmax 200005

punct A[Nmax],B[Nmax];
int n,na,nb;
bool use[Nmax];

LL produs_vec(punct A,punct B){
   LL x1=A.x,x2=B.x,y1=A.y,y2=B.y;
   return x1*y2-x2*y1;
}

int cmp(punct A,punct B){
    return produs_vec(A,B)>0;
}

int solve(punct P[],int N){
    sort(P+1,P+N+1,cmp);
    int i=1,j=1,sol=0;
    while(j<=N){
                if(P[j].tip==1 && use[P[j].nr]==0){
                              while(i<=j){
                                          use[P[i].nr]=1;
                                          ++i;
                                          }
                              ++sol;
                              }
                ++j;
    }
    return sol;
}
           
long rez;
int main(){
     int i,xx,y1,y2;
     freopen("rays.in","r",stdin);
     freopen("rays.out","w",stdout);
     scanf("%ld",&n);
     for(i=1;i<=n;++i){
       scanf("%d%d%d",&xx,&y1,&y2);
       if(y1>y2) swap(y1,y2);
       if(xx>0) A[++na]=MP(xx,y1,0,i), A[++na]=MP(xx,y2,1,i);
       else B[++nb]=MP(-xx,y1,0,i), B[++nb]=MP(-xx,y2,1,i);
       }
       
     rez=solve(A,na);
     memset(use,0,sizeof(use));
     rez+=solve(B,nb);
     printf("%ld\n",rez);
     fclose(stdin); fclose(stdout);
     return 0;
}