Cod sursa(job #328855)

Utilizator mihai_floreaFlorea Mihai Alexandru mihai_florea Data 3 iulie 2009 15:58:29
Problema Rays Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <fstream>
#include <algorithm>
using namespace std;
#define x first.first
#define y first.second
#define tip second.first
#define idx second.second
typedef pair< pair<int,int>,pair<int,int> > punct;
typedef long long i64;
#define mp make_pair
#define MP(a,b,c,d) mp(mp(a,b),mp(c,d))
const int NMAX=200002;
punct A[NMAX],B[NMAX];
int N,NA,NB;
ifstream f("rays.in");
ofstream g("rays.out");
i64 prod_vec(punct A,punct B)
{
    i64 x1=A.x,y1=A.y,x2=B.x,y2=B.y;
    return x1*y2-x2*y1;
}
int cmp(punct A,punct B)
{
    return prod_vec(A,B)>0;
}
int Q[NMAX],NQ;
bool U[NMAX];
int solve(punct P[],int N)
{
   sort(P+1,P+N+1,cmp);
   int i,j,sol=0;
   for (i=1,NQ=0;i<=N;++i)
     if (P[i].tip==0) Q[++NQ]=P[i].idx;
     else
     {
         if (U[P[i].idx]) continue;
         ++sol;
         for (j=1;j<=NQ;++j) U[Q[j]]=true;
         NQ=0;
     }
    return sol;  
}
int main()
{
    f>>N;
    int i,xx,y1,y2;
    for (i=1;i<=N;++i)
    {
        f>>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);
    }
    g<<solve(A,NA)+solve(B,NB);
    return 0;
}