Cod sursa(job #2556432)

Utilizator AlexPascu007Pascu Ionut Alexandru AlexPascu007 Data 24 februarie 2020 21:33:14
Problema Pachete Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("pachete.in");
ofstream fout("pachete.out");
int n,x,y,px,py,i,sol,d[50010];
vector< pair<int,int> > c1,c2,c3,c4;
int cadran(vector< pair<int,int> > v) {
    if (v.size()==0)
        return 0;
    sort(v.begin(),v.end());
    d[1]=v[0].second;
    int cnt=1,st,dr;
    for (int i=1;i<v.size();i++) {
        st=1, dr=cnt;
        while (st<=dr) {
            int mid=(st+dr)/2;
            if (d[mid]>v[i].second)
                st=mid+1;
            else
                dr=mid-1;
        }
        if (st>cnt)
            cnt++;
    }
    return cnt;
}
int main() {
    fin>>n;
    fin>>x>>y;
    for (i=1;i<=n;i++) {
        fin>>px>>py;
        if (px>0) {
            if (py>0)
                c1.push_back({px,py});
            else
                c4.push_back({px,py});
        }
        else {
            if (py>0)
                c2.push_back({px,py});
            else
                c3.push_back({px,py});
        }
    }
    sol=cadran(c1);
    for (i=0;i<c2.size();i++)
        c2[i].first=-c2[i].first;
    sol+=cadran(c2);
    for (i=0;i<c3.size();i++) {
        c3[i].first=-c3[i].first;
        c3[i].second=-c3[i].second;
    }
    sol+=cadran(c3);
    for (i=0;i<c4.size();i++)
        c4[i].second=-c4[i].second;
    sol+=cadran(c4);
    fout<<sol;
    return 0;
}