Cod sursa(job #1220960)

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

#define NMAX 50000

using namespace std;

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

punct pct[4][NMAX]; 

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");
    
    int n, sol = 0, x, y, ox, oy;
    fscanf(fin, "%d", &n);
    fscanf(fin, "%d %d", &ox, &oy);
    for(int i = 0; i < n; ++i) {
       fscanf(fin, "%d %d", &x, &y);
       x -= ox;
       y -= oy;
       if( x > 0 && y > 0 ) {
            pct[0][nr[0]].x = x; pct[0][nr[0]++].y = y;
        }
       if( x > 0 && y <= 0 ) {
            pct[1][nr[1]].x = x; pct[1][nr[1]++].y = y;
        }
       if( x <= 0 && y < 0) {
            pct[2][nr[2]].x = x; pct[2][nr[2]++].y = y;
        }
       if( x <= 0 && y > 0 ) {
            pct[3][nr[3]].x = x; pct[3][nr[3]++].y = y;
        } 
    }
    
    for(int p = 0; p <= 3; p++) {
    sort(pct[p], pct[p] + nr[p], 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, "%d", sol);
}