Cod sursa(job #113376)

Utilizator astronomyAirinei Adrian astronomy Data 9 decembrie 2007 20:01:24
Problema Rays Scor Ascuns
Compilator cpp Status done
Runda Marime 1.7 kb
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
using namespace std;

#define pb push_back
#define mp make_pair
#define PII pair<int, int>
#define llong long long
#define PO pair< PII, int >
#define x first
#define y second
#define MAXN 200100

int N, res, st[MAXN], perm[MAXN], pus[MAXN];
vector< PO > A, B;

int cross(PO a, PO b)
{
    llong t = (llong)a.x.x*b.x.y-(llong)a.x.y*b.x.x;
    return t < 0 ? -1 : t > 0 ? 1 : 0;
}

int cmp(int i, int j)
{
    return cross( A[i], A[j] ) == 1;
}

void solve(void)
{
    int i, j, k, vf, dd, dc;

    if(A.size() == 0) return ;
    
    memset(pus, 0, sizeof(pus));
    
    for(i = 0; i < A.size(); i++) perm[i] = i;

    sort(perm, perm+A.size(), cmp);

    for(vf = 0, i = 0; i < A.size(); i++)
    {
        j = A[perm[i]].y;
        dc = A[perm[i]].x.x, dd = A[perm[i]].x.y;
        
        if(pus[j] == 2) continue ;
        if(!pus[j]) { pus[j]++; st[++vf] = j; continue ; }
        for(res++; vf > 0; vf--) pus[st[vf]] = 2;
        for(k = i; i < A.size() && cross(A[perm[k]], A[perm[i]]) == 0; i++)
            pus[A[perm[i]].y] = 2;
        i--;
    }
}

void ruleaza(void)
{
    int i, a, b, c;
    
    scanf("%d ", &N);

    for(i = 0; i < N; i++)
    {
        scanf("%d %d %d", &a, &b, &c);
        if(a > 0) A.pb( mp(mp(a, b), i) ), A.pb( mp(mp(a, c), i) );
        else B.pb( mp(mp(a, b), i) ), B.pb( mp(mp(a, c), i) );
    }

    solve();
    A = B;
    solve();

    printf("%d\n", res);
}

int main(void)
{
    freopen("rays.in", "rt", stdin);
    freopen("rays.out", "wt", stdout);

    ruleaza();

    return 0;
}