Cod sursa(job #1487617)

Utilizator akaprosAna Kapros akapros Data 17 septembrie 2015 09:51:52
Problema Pachete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.77 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define maxN 50005
#define pb push_back
#define mp make_pair
#define x first
#define y second
#define nrC 4
using namespace std;
int x, y, w[maxN], n, i, j, sol;
int vix, viy;
int cmp (pair <int, int> a, pair <int, int> b)
{
    if (a.x == b.x)
        return a.y < b.y;
    return a.x < b.y;
}
vector < pair <int, int> > V[nrC + 2];
void read()
{
    int i, a, b;
    freopen("pachete.in", "r", stdin);
    scanf("%d", &n);
    scanf("%d %d", &a, &b);
    for (i = 1; i <= n; ++ i)
    {
        scanf("%d %d", &vix, &viy);
        vix -= a;
        viy -= b;
        if (vix > 0 && viy > 0)
            V[0].pb(mp(vix, viy));
        else if (vix > 0 && viy < 0)
            V[1].pb(mp(vix, -viy));
        else if (vix < 0 && viy > 0)
            V[2].pb(mp(-vix, viy));
        else
            V[3].pb(mp(-vix, -viy));
    }
}
int bs(int a)
{
    int i = 1, p = 1 << 15;
    while (p)
    {
        if (i + p <= w[0] && w[i + p] >= a)
            i += p;
        p /= 2;
    }
    if (i + 1 <= w[0] && w[i] >= a)
            ++ i;
    return i;
}

void solc(int a)
{
    int i, p;
    w[0] = 0;
    for (i = 0; i < V[a].size(); ++ i)
    {
        if (i == 0 || V[a][i].y <= w[w[0]])
           w[++ w[0]] = V[a][i].y;
        else
        {
            p = bs(V[a][i].y);
            w[p] = V[a][i].y;
        }
    }
}

void solve()
{
    int i;
    for (i = 0; i < nrC; ++ i)
    {
        sort(V[i].begin(), V[i].end());
        solc(i);
        sol += w[0];
        w[0] = 0;
    }
}
void write()
{
    freopen("pachete.out", "w", stdout);
    printf("%d", sol);
}
int main()
{
    read();
    solve();
    write();
    return 0;
}