Cod sursa(job #1150545)

Utilizator TibixbAndrei Tiberiu Tibixb Data 23 martie 2014 11:39:50
Problema Pachete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.83 kb
#include<fstream>
#include<algorithm>
using namespace std;
int n, xc, yc, i, sol, a[50003], b[50003], k, p[50003], nrp, st, m, dr;
pair<int,int> v[50010];
ifstream in("pachete.in");
ofstream out("pachete.out");
int main(){
    in>>n;
    in>>xc>>yc;
    for(i=1; i<=n; i++){
        in>>a[i]>>b[i];
        a[i]-=xc;
        b[i]-=yc;
    }
    xc=0;
    yc=0;
    for (int t=1;t<=4;t++) {

        k=0;

        for(i=1; i<=n; i++){
            if (t == 1) {
                if(a[i]>0 && b[i]>0){
                    v[++k].first=a[i];
                    v[k].second=b[i];
                }
            } else {
                if (t == 2) {
                    if(a[i]<0 && b[i]>0){
                        v[++k].first=-a[i];
                        v[k].second=b[i];
                    }
                } else {
                    if (t == 3) {
                        if(a[i]>0 && b[i]<0){
                            v[++k].first=a[i];
                            v[k].second=-b[i];
                        }
                    } else {
                        if(a[i]<0 && b[i]<0){
                            v[++k].first=-a[i];
                            v[k].second=-b[i];
                        }                    }
                }
            }
        }
        if (k==0)
            continue;
        sort(v+1, v+k+1);
        p[nrp=1]=v[1].second;
        for(i=2; i<=k; i++){
            st=1;
            dr=nrp;
            while(st<=dr){
                m=(st+dr)/2;
                if(v[i].second<p[m])
                    st=m+1;
                else
                    dr=m-1;
            }
            if(st<=nrp)
                p[st]=v[i].second;
            else
                p[++nrp]=v[i].second;
        }
        sol+=nrp;
    }
    out<<sol;
return 0;
}