Pagini recente » Cod sursa (job #2583622) | Cod sursa (job #619881) | Cod sursa (job #109282) | Cod sursa (job #634100) | Cod sursa (job #1765363)
#include <stdio.h>
int x[50000], y[50000], px[4] = {1, -1, -1, 1}, py[4] = {1, 1, -1, -1};
int ly[50000];
inline int calc(int st, int dr){
int i, j, pas, d = 0;
for(i = st; i <= dr; i++){
j = -1;
for(pas = (1 << 15); pas > 0; pas >>= 1)
if(j + pas < d && ly[j + pas] > y[i])
j += pas;
j++;
ly[j] = y[i];
if(j == d)
d++;
}
return d;
}
void qs(int st, int dr){
int i = st, j = dr, piv = x[(st + dr) / 2], aux;
while(i <= j){
while(x[i] < piv)
i++;
while(x[j] > piv)
j--;
if(i <= j){
aux = x[i]; x[i] = x[j]; x[j] = aux;
aux = y[i]; y[i] = y[j]; y[j] = aux;
i++; j--;
}
}
if(st < j)
qs(st, j);
if(i < dr)
qs(i, dr);
}
int main(){
FILE *fin, *fout;
fin=fopen("pachete.in", "r");
fout=fopen("pachete.out", "w");
int n, i, xs, ys, j, k;
fscanf(fin, "%d%d%d", &n, &xs, &ys);
for(i = 0; i < n; i++){
fscanf(fin, "%d%d", &x[i], &y[i]);
x[i] -= xs;
y[i] -= ys;
}
int aux, rez = 0;
for(k = 0; k < 4; k++){
for(i = 0; i < n; i++){
x[i] *= px[k];
y[i] *= py[k];
}
j = n - 1;
for(i = n - 1; i >= 0; i--){
if(x[i] > 0 && y[i] > 0){
aux = x[i]; x[i] = x[j]; x[j] = aux;
aux = y[i]; y[i] = y[j]; y[j] = aux;
j--;
}
}
qs(j + 1, n - 1);
rez += calc(j + 1, n - 1);
n = j + 1;
for(i = 0; i < n; i++){
x[i] *= px[k];
y[i] *= py[k];
}
}
fprintf(fout, "%d", rez);
fclose(fout);
fclose(fin);
return 0;
}