Cod sursa(job #1947591)

Utilizator failureJust a Joke failure Data 31 martie 2017 08:03:43
Problema Pachete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.97 kb
#include <bits/stdc++.h>

#define x first
#define y second
#define MAXN 50001

using namespace std;

vector < pair<int, int> > v[4];
pair <int, int> start;

int k, path[MAXN], lg[MAXN];

int binarySearch(int value)
{
    int ans = 0, step;

    if(!k) return 0;

    for(step=(1<<lg[k]); step>=1; step>>=1)
        if(ans + step <= k && path[ans + step] > value)
            ans += step;

    if(ans == k)
        return 0;

    return ans+1;
}

int checkWays(int index)
{
    int pos, i;

    sort(v[index].begin(), v[index].end());

    k = 0;
    for(i=0; i<v[index].size(); ++i) {
        pos = binarySearch(v[index][i].y);
        if(pos)
            path[pos] = v[index][i].y;
        else path[++k] = v[index][i].y;
    }

    return k;
}

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

    int i, n, ox, oy, answer = 0;
    pair <int, int> point;

    scanf("%d%d%d", &n, &start.x, &start.y);
    for(i=1; i<=n; ++i) {
        scanf("%d%d", &point.x, &point.y);
        if(point.x < start.x) {
            if(point.y >= start.y) {
                ox = abs(start.x - point.x);
                oy = abs(point.y - start.y);
                v[1].push_back({ox, oy});
            }else{
                ox = abs(start.x - point.x);
                oy = abs(start.y - point.y);
                v[2].push_back({ox, oy});
            }
        }
        else {
            if(point.y >= start.y) {
                ox = abs(point.x - start.x);
                oy = abs(point.y - start.y);
                v[0].push_back({ox, oy});
            }else{
                ox = abs(point.x - start.x);
                oy = abs(start.y - point.y);
                v[3].push_back({ox, oy});
            }
        }
    }

    lg[2] = 1;
    for(i=3; i<=n; ++i)
        lg[i] = lg[i/2] + 1;

    for(i=0; i<4; ++i)
        answer += checkWays(i);

    printf("%d", answer);

    return 0;
}