Cod sursa(job #1220963)

Utilizator jul123Iulia Duta jul123 Data 19 august 2014 08:41:44
Problema Pachete Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 kb
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<set>
#include<vector>

#define NMAX 100000

using namespace std;

set<long long> st;
set<long long>::iterator aux;
typedef struct un_pct {
    long long x;
    long long y;
}punct;

vector <punct> pct[4]; 

int cmp(punct a, punct b)
{
    return( a.x < b.x);
}

int nr[4];

int main()
{
    FILE *fin, *fout;
    fin = fopen("pachete.in", "r");
    fout = fopen("pachete.out", "w");
    
    long long n, sol = 0, x, y, ox, oy;
    fscanf(fin, "%lld", &n);
    fscanf(fin, "%lld %lld", &ox, &oy);
    for(int i = 0; i < n; ++i) {
       fscanf(fin, "%lld %lld", &x, &y);
       x -= ox;
       y -= oy;
       punct aa;
       aa.x = x;
       aa.y = y;
       if( x > 0 && y > 0 ) {
            pct[0].push_back(aa);
        }
       if( x > 0 && y <= 0 ) {
            pct[1].push_back(aa);
        }
       if( x <= 0 && y < 0) {
            pct[2].push_back(aa);
        }
       if( x <= 0 && y > 0 ) {
            pct[3].push_back(aa);
        } 
    }
    for(int p = 0; p <= 3; ++p)
        nr[p] = pct[p].size();
    
    for(int p = 0; p <= 3; p++) {
    sort(pct[p].begin(), pct[p].end(), cmp);
    
    for(int i = 0; i < nr[p]; ++i)
    {
         aux = upper_bound (st.begin(), st.end(), pct[p][i].y);
        if(aux == st.begin()) {
            ++sol;
        }
        else {
            st.erase(aux);
        }
        st.insert(pct[p][i].y);
    }
}
    fprintf(fout, "%lld", sol);
}