Cod sursa(job #1786621)

Utilizator ionanghelinaIonut Anghelina ionanghelina Data 23 octombrie 2016 13:35:58
Problema Pachete Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.95 kb
#include<bits/stdc++.h>
using namespace std;
int n,x,y;
int subsir[50005];
int seen[50005],drumuri,a1,a2,b1,b2,st,dr,mid,sol,sol1;
pair<int,int> v[50005];
vector<int> c1,c2,c3,c4;
bool cmp(int x,int y)
{
    if(v[x].first<v[y].first) return 1;
    if(v[x].first==v[y].first && v[x].second<v[y].second) return 1;
    return 0;
}
void solve(vector<int> a)
{
    int ds=1;
    int drum=1;
    sort(a.begin(),a.end(),cmp);
    subsir[1]=a[0];
    for(int i=1;i<a.size();i++)
    {
        sol=0;
        st=1;
        dr=ds;
        while(st<=dr)
        {
            mid=(st+dr)>>1;
            if(v[subsir[mid]].second<=v[a[i]].second)
            {
                sol=mid;
                st=mid+1;
            }
                else dr=mid-1;
        }
        if(sol)
        {
            subsir[sol]=a[i];
        }
            else
        {
            drum++;
            ds++;
            subsir[ds]=a[i];
        }
    }
    drumuri+=drum;
}
int main()
{
    freopen("pachete.in","r",stdin);
    freopen("pachete.out","w",stdout);
    scanf("%d",&n);
    scanf("%d%d",&x,&y);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&v[i].first,&v[i].second);
        v[i].first-=x;
        v[i].second-=y;
        if(v[i].first>0 && v[i].second>0)
        {
            c1.push_back(i);
        }
            else
        if(v[i].first>0 && v[i].second<=0)
        {
            v[i].second=-v[i].second;
            c2.push_back(i);
        }
            else
        if(v[i].first<=0 && v[i].second>0)
        {
            v[i].first=-v[i].first;
            c3.push_back(i);
        }
            else
        {
            v[i].first=-v[i].first;
            v[i].second=-v[i].second;
            c4.push_back(i);
        }
    }
    if(!c1.empty())solve(c1);
    if(!c2.empty())solve(c2);
    if(!c3.empty())solve(c3);
    if(!c4.empty())solve(c4);
    printf("%d\n",drumuri);
    return 0;
}