Cod sursa(job #2557892)

Utilizator mirceaisherebina mircea mirceaishere Data 26 februarie 2020 09:26:43
Problema Pachete Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.57 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("pachete.in");
ofstream fout("pachete.out");

int n, i, st, dr, mid, x, y, xSediu, ySediu, v[50010], k, aux;
vector < pair<int, int> > cadran1;
vector < pair<int, int> > cadran2;
vector < pair<int, int> > cadran3;
vector < pair<int, int> > cadran4;

int solutie(vector < pair<int, int> > cadran){
    if(cadran.size()==0){
        return 0;
    }
    sort(cadran.begin(), cadran.end());
    k=1;
    v[1]=cadran[0].second;
    for(int i=1; i<cadran.size(); i++){
        aux=cadran[i].second;
        st=1;
        dr=k;
        while(st<=dr){
            mid=(st+dr)/2;
            if(v[mid>aux]){
                st=mid+1;
            }else{
                dr=mid-1;
            }
        }
        if(st==k+1){
            k++;
        }
        v[k]=aux;
    }
    return k;
}

/// normalizez punctele, consider sediul ca originea sistemului
/// incadrez punctele in cadrane si le rezolv separat

int main(){
    fin>>n;
    fin>>xSediu>>ySediu;
    for(i=1; i<=n; i++){
        fin>>x>>y;
        x-=xSediu;
        y-=ySediu;
        if(x>0){
            if(y>0){
                cadran1.push_back({x, y});
            }else{
                cadran4.push_back({x, -y});
            }
        }else{
            if(y>0){
                cadran2.push_back({-x, y});
            }else{
                cadran3.push_back({-x, -y});
            }
        }
    }
    fout<<solutie(cadran1)+solutie(cadran2)+solutie(cadran3)+solutie(cadran4);
}