Cod sursa(job #6660)

Utilizator filipbFilip Cristian Buruiana filipb Data 20 ianuarie 2007 14:58:52
Problema Pachete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.65 kb
#include <stdio.h>
#include <algorithm>
#define change(a, b) ( (a) ^= (b) ^= (a) ^= (b) )
#define NMax 50024 
typedef struct { int x, y; } entry;

using namespace std;

int N, Ox, Oy;
entry v[NMax];
int C[4][NMax], h[4], last[NMax], nr_s, cnt = 0;

int cmp(entry A, entry B)
{ return A.x < B.x; }

int cadran(int x, int y)
{
    if (x > 0 && y > 0) return 0;
    if (x < 0 && y > 0) return 1;
    if (x < 0 && y < 0) return 2;
    return 3;
}

int main(void)
{
    int i, r, li, ho, m, u;
    
    freopen("pachete.in", "r", stdin);
    freopen("pachete.out", "w", stdout);
    
    for (scanf("%d %d %d", &N, &Ox, &Oy), i = 0; i < N; i++)
        scanf("%d %d", &v[i].x, &v[i].y);
    sort(v+0, v+N, cmp);
    
    for (i = 0; i < N; i++)
    {
        r = cadran(v[i].x - Ox, v[i].y - Oy);
        if (r == 0 || r == 1)
             C[r][++h[r]] = v[i].y - Oy;
        else C[r][++h[r]] = Oy - v[i].y;
    }
    
    for (r = 1; r <= 2; r++)
        for (i = 1; i <= h[r]/2; i++)
            change(C[r][i], C[r][h[r]-i+1]);
        
    for (r = 0; r < 4; r++)
    {       
        if (h[r] == 0) continue;
        
        last[nr_s = 1] = C[r][1];
        for (i = 2; i <= h[r]; i++)
        {
            li = 1; ho = nr_s; u = nr_s+1;
            while (li <= ho)
            {
                  m = ((li + ho) >> 1);
                  if (last[m] <= C[r][i]) u = m, ho = m-1;
                  else li = m+1;
            }
            last[u] = C[r][i];
            if (u > nr_s) nr_s = u;            
        }
                
        cnt += nr_s;
    }
     
    printf("%d\n", cnt);
     
    return 0;
}