Cod sursa(job #13828)

Utilizator sims_glAlexandru Simion sims_gl Data 7 februarie 2007 16:39:47
Problema Pachete Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <stdio.h>
#include <algorithm>

using namespace std;

#define nm 50100

struct point
{
	int x, y;
};

int n, m[5], st[nm], sol;
point c[5][nm], d, aux;

int comp(point a, point b)
{
	return a.x < b.x;
}

int main()
{
	int i, crt;
    point aux;

	freopen("pachete.in", "r", stdin);
    freopen("pachete.out", "w", stdout);

    scanf("%d%d%d", &n, &d.x, &d.y);

    for (i = 1; i <= n; ++i)
    {
    	scanf("%d%d", &aux.x, &aux.y);

        aux.x -= d.x;
        aux.y -= d.y;

        if (aux.x >= 0 && aux.y >= 0)
        	c[1][++m[1]] = aux;
        else if (aux.x < 0 && aux.y >= 0)
        	c[2][++m[2]] = aux;
        else if (aux.x < 0 && aux.y < 0)
        	c[3][++m[3]] = aux;
        else
        	c[4][++m[4]] = aux;
    }

    sort(c[1] + 1, c[1] + m[1] + 1, comp);
    sort(c[2] + 1, c[2] + m[2] + 1, comp);
    sort(c[3] + 1, c[3] + m[3] + 1, comp);
    sort(c[4] + 1, c[4] + m[4] + 1, comp);

    for (crt = 1; crt <= 4; ++crt)
    	if (m[crt])
        {
        	st[0] = 1;
            st[1] = 1;
    
            for (i = 2; i <= m[crt]; ++i)
            {
            	++st[0];
                
            	while(st[0] > 1 && c[crt][i].y > c[crt][st[st[0] - 1]].y)
                	--st[0];
    
                st[st[0]] = i;
            }
    
            sol += st[0];
        }

    printf("%d\n", sol);
    
	return 0;
}