Cod sursa(job #1220975)

Utilizator jul123Iulia Duta jul123 Data 19 august 2014 09:31:22
Problema Pachete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.46 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 )
        if( y > 0 ) {
            pct[0][nr[0]].x = x; pct[0][nr[0]++].y = y;
        }
        else {
            pct[1][nr[1]].x = x; pct[1][nr[1]++].y = -y;
        }
       else{
        if(y < 0) {
            pct[2][nr[2]].x = -x; pct[2][nr[2]++].y = -y;
        }
        else {
            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);
     st.clear();
    for(int i = 0; i < nr[p]; ++i)
    {
        //sol = 0;
         aux = st.lower_bound(pct[p][i].y);
        if(aux == st.begin()) {
            ++sol;
        }
        else {
            --aux;
            st.erase(aux);
        }
        st.insert(pct[p][i].y);
        
    }
}
    fprintf(fout, "%d", sol);
}