Cod sursa(job #1940008)

Utilizator raluca1234Tudor Raluca raluca1234 Data 26 martie 2017 12:12:16
Problema Pachete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.72 kb
#include <cstdio>
#include <vector>
#include <algorithm>

#define maxN 50000

using namespace std;

struct POINT{
    int x, y;
}S, v[maxN+1];

int subsir[maxN+1];
int ans;

vector <int> c1,c2,c3,c4;

inline bool cmp(int p1, int p2){
    if (v[p1].x==v[p2].x) return v[p1].y<v[p2].y;
    return v[p1].x<v[p2].x;
}

void solve(vector<int> c){
    sort(c.begin(), c.end(), cmp);

    int nrs=0;
    subsir[++nrs]=c[0];

    int nr=c.size();
    for (int i=1; i<nr; i++){
        int last=0;
        int st=1, dr=nrs, mid;
        while (st<=dr){
            mid=(st+dr)/2;
            if (v[subsir[mid]].y<=v[c[i]].y){
                last=mid;
                dr=mid-1;
            }
            else st=mid+1;
        }
        if (last)
            subsir[last]=c[i];
        else
            subsir[++nrs]=c[i];
    }
    ans+=nrs;
}
int main(){
    freopen("pachete.in", "r", stdin);
    freopen("pachete.out", "w", stdout);

    int N;
    scanf("%d", &N);
    scanf("%d%d", &S.x, &S.y);

    for (int i=1; i<=N; i++){
        scanf("%d%d", &v[i].x, &v[i].y);

        v[i].x-=S.x;
        v[i].y-=S.y;

        if (v[i].x>0 && v[i].y>0)
            c1.push_back(i);
        else
        if (v[i].x>0 && v[i].y<=0){
            v[i].y*=(-1);
            c2.push_back(i);
        }else
        if (v[i].x<=0 && v[i].y>0){
            v[i].x*=(-1);
            c3.push_back(i);
        }
        else{
            v[i].x*=(-1);
            v[i].y*=(-1);
            c4.push_back(i);
        }
    }

    if (!c1.empty()) solve(c1);
    if (!c2.empty()) solve(c2);
    if (!c3.empty()) solve(c3);
    if (!c4.empty()) solve(c4);

    printf("%d\n", ans);

    return 0;
}