Cod sursa(job #1915320)

Utilizator Ruxandra985Nanu Ruxandra Laura Ruxandra985 Data 8 martie 2017 20:37:14
Problema Pachete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.98 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;
pair<int, int> a[50001],b[50001];
int v[50001];
int fct (int n){
    int nr,i,elem,st,dr,mid;
    if (n==0)
        return 0;
    sort (b+1,b+n+1);
    nr=0;
    elem=0;
    for (i=1;i<=n;i++){
        st=1;
        dr=elem;
        while (st<=dr){
            mid=(st+dr)/2;
            if (v[mid]<b[i].second)
                dr=mid-1;
            else
                st=mid+1;
        }
        // solutia este st
        if (st==elem+1){
            v[++elem]=b[i].second;
            nr++;
        }
        else v[st]=b[i].second;
    }
    return nr;
}
int main()
{
    FILE *fin=fopen ("pachete.in","r");
    FILE *fout=fopen ("pachete.out","w");
    int n,x,y,xx,yy,i,elem,sol=0;
    fscanf (fin,"%d%d%d",&n,&x,&y);
    for (i=1;i<=n;i++){
        fscanf (fin,"%d%d",&xx,&yy);
        xx-=x;
        yy-=y;
        a[i].first=xx;
        a[i].second=yy;
    }
    elem=0;
    for (i=1;i<=n;i++){
        if (a[i].first>0 && a[i].second>0){
            // apartine sectiunii alese
            b[++elem].first=a[i].first;
            b[elem].second=a[i].second;
        }
    }
    sol+=fct(elem);
    elem=0;
    for (i=1;i<=n;i++){
        if (a[i].first<0 && a[i].second>0){
            // apartine sectiunii alese
            b[++elem].first=-a[i].first;
            b[elem].second=a[i].second;
        }
    }
    sol+=fct(elem);
    elem=0;
    for (i=1;i<=n;i++){
        if (a[i].first>0 && a[i].second<0){
            // apartine sectiunii alese
            b[++elem].first=a[i].first;
            b[elem].second=-a[i].second;
        }
    }
    sol+=fct(elem);
    elem=0;
    for (i=1;i<=n;i++){
        if (a[i].first<0 && a[i].second<0){
            // apartine sectiunii alese
            b[++elem].first=-a[i].first;
            b[elem].second=-a[i].second;
        }
    }
    sol+=fct(elem);
    fprintf (fout,"%d",sol);
    return 0;
}