Cod sursa(job #918237)

Utilizator apopeid13Apopeid Alejandro apopeid13 Data 18 martie 2013 18:35:30
Problema Pachete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <stdlib.h>
using namespace std;
 
ifstream fi ("pachete.in");
ofstream fo ("pachete.out");
 
const int dim = 50005;
int N;
long long L[dim], XC, YC;
struct punct { long long x, y; } P[dim];
vector <punct> LP[4];
 
void cit ()
{
    fi >> N >> XC >> YC;
    for (int i = 1, gr; i <= N; i++)
    {
        fi >> P[i].x >> P[i].y;
        P[i].x -= XC;
        P[i].y -= YC;
         
        if (P[i].x >= 0 && P[i].y >= 0) gr = 0;
        if (P[i].x >  0 && P[i].y <  0) gr = 1;
        if (P[i].x <  0 && P[i].y >  0) gr = 2;
        if (P[i].x <= 0 && P[i].y <= 0) gr = 3;
         
        P[i].x = abs (P[i].x);
        P[i].y = abs (P[i].y);
        LP[gr].push_back (P[i]);
    }  
}
 
int cmp (punct a, punct b)
{
    if (a.x == b.x)
        return a.y < b.y;
    return a.x < b.x;
}
 
int cauta (long long V[], long long val)
{
    int p = 1, u = V[0], m;
    while (p <= u)
    {
        m = ((u - p) >> 1) + p;
        if (val < V[m])
            p = m + 1;
        else
            u = m - 1;
    }
    return p;
}
 
void rez ()
{
    int gr, i, r = 0, p;
    for (gr = 0; gr < 4; gr++)
    {
        sort (LP[gr].begin(), LP[gr].end(), cmp);
        L[0] = 0;
        for (i = 0; i < LP[gr].size(); i++)
        {
            p = cauta (L, LP[gr][i].y);
            if (p == L[0] + 1)
                L[++L[0]] = LP[gr][i].y;
            else
                L[p] = LP[gr][i].y;
        }
        r += L[0];
    }
    fo << r << '\n';
}
 
int main ()
{
    cit ();
    rez ();
    return 0;
}