Cod sursa(job #838727)

Utilizator stoicatheoFlirk Navok stoicatheo Data 20 decembrie 2012 13:43:17
Problema Pachete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 kb
#include <stdio.h>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
 
#define NMAX 50010
 
 
int N;
 
int nr[4];
pair <int, int> nod[4][NMAX];
 
set <int> H;
 
int make(int q)
{
    int rez = 0;
     
    sort(nod[q] + 1, nod[q] + nr[q] + 1);
 
//  for (int i = 1; i <= nr[q]; i++) printf("%d %d | ", nod[q][i].first, nod[q][i].second);
//  printf("\n");
 
    H.clear();
 
    set <int> :: iterator it;
 
    for (int i = 1; i <= nr[q]; i++) {
        it = H.lower_bound(nod[q][i].second);
 
        if (it == H.begin()) {
            rez++;
        } else {
            --it;
            H.erase(it);
        }
 
        H.insert(nod[q][i].second);
    }   
 
return rez;
}
 
int main()
{
    int i, x, y, xb, yb;
     
    freopen("pachete.in", "r", stdin);
    freopen("pachete.out", "w", stdout);
 
    scanf("%d", &N);
 
    scanf("%d %d", &xb, &yb);
 
    for (i = 1; i <= N; i++) {
        scanf("%d %d", &x, &y);
 
        x -= xb;
        y -= yb;
 
        if (x > 0 && y > 0) nr[0]++, nod[0][nr[0]].first = x, nod[0][nr[0]].second = y;
        if (x < 0 && y > 0) nr[1]++, nod[1][nr[1]].first = -x, nod[1][nr[1]].second = y;
        if (x < 0 && y < 0) nr[2]++, nod[2][nr[2]].first = -x, nod[2][nr[2]].second = -y;
        if (x > 0 && y < 0) nr[3]++, nod[3][nr[3]].first = x, nod[3][nr[3]].second = -y;
    }
 
    int rez = 0;
 
    rez += make(0);
    rez += make(1);
    rez += make(2);
    rez += make(3);
 
    printf("%d\n", rez);
 
fclose(stdin);
fclose(stdout);
return 0;
}