Cod sursa(job #2276770)

Utilizator divianegoescuDivia Negoescu divianegoescu Data 5 noiembrie 2018 12:20:44
Problema Pachete Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.98 kb
#include <fstream>
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
FILE *fin=fopen("pachete.in","r");
ofstream fout("pachete.out");
int n,i,x0,y0,xi,yi,a,b,st,dr,mid,poz,x,drumuri;
bool ok;
pair <int,int> v1[50001],v2[50001],v3[50001],v4[50001];
int p1[50001];
int main()
{
    fscanf(fin,"%d%d%d",&n,&x0,&y0);
    for(i=1;i<=n;i++)
    {
        fscanf(fin,"%d%d",&xi,&yi);
        a=xi-x0;
        b=yi-y0;
        if(a>=0 && b>=0)
        {
            v1[++v1[0].first].first=a;
            v1[v1[0].first].second =b;
        }
        else if(a>=0 && b<0)
        {
            v2[++v2[0].first].first=a;
            v2[v2[0].first].second =b;
        }
        else if(a<0 && b<0)
        {
            v3[++v3[0].first].first=a;
            v3[v3[0].first].second =b;
        }
        else if(a<0 && b>=0)
        {
            v4[++v4[0].first].first=a;
            v4[v4[0].first].second =b;
        }
    }
    sort(v1+1,v1+v1[0].first+1);
    sort(v2+1,v2+v2[0].first+1);
    sort(v3+1,v3+v3[0].first+1);
    sort(v4+1,v4+v4[0].first+1);
/// /////////// CAD 1
    if(v1[0].first>0)
    {
        p1[++p1[0]]=v1[1].second;
        for(i=2; i<=v1[0].first; i++)
        {
            p1[p1[0]+1]=-1;
            st=0;dr=p1[0];
            x=v1[i].second;
            poz=-1;
            while(st<=dr)
            {
                mid=(st+dr)/2;
                if(p1[mid]<=x && p1[mid-1]>x)
                {
                    poz=mid; break;
                }
                else if(p1[mid]>x)
                    st=mid+1;
                else {poz=mid;dr=mid-1;}
            }
            if(poz>-1)
            {///cel mai mare elem mai mic sau egal cu x este pe pozitia poz; continuam drumul
                p1[poz]=x;
            }
            else
            {///drum nou
                p1[p1[0]+1]=x;
                drumuri++;
            }
        }
    }
    fout<<drumuri;
    return 0;
}