Pagini recente » Cod sursa (job #608130) | Cod sursa (job #1673405) | Cod sursa (job #2340327) | Cod sursa (job #1318475) | Cod sursa (job #1428862)
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAXL 200000
#define BUFF (1 << 22)
FILE *in;
int x[MAXL], y[MAXL], point[MAXL];
char tip[MAXL];
int p = BUFF;
char buff[BUFF];
inline char cif(char ch){
if(ch >= '0' && ch <= '9')
return 1;
return 0;
}
inline char getch(){
if(p == BUFF){
fread(buff, 1, BUFF, in);
p = 0;
}
p++;
return buff[p - 1];
}
inline int getnum(){
int rez = 0;
char ch = getch();
while(!cif(ch))
ch = getch();
while(cif(ch)){
rez *= 10;
rez += ch - '0';
ch = getch();
}
return rez;
}
inline char cmp(int x1, int t1, int x2, int t2){
if(x1 > x2)
return 1;
if(x2 > x1)
return 0;
if(t1 > t2)
return 1;
if(t2 > t1)
return 0;
return 0;
}
void qs(int st, int dr){
int i = st, j = dr, m = st + rand() % (dr - st + 1), pivx = x[point[m]], pivt = tip[point[m]], aux;
while(i <= j){
while(cmp(x[point[i]], tip[point[i]], pivx, pivt))
i++;
while(cmp(pivx, pivt, x[point[j]], tip[point[j]]))
j--;
if(i <= j){
aux = point[i]; point[i] = point[j]; point[j] = aux;
i++; j--;
}
}
if(st < j)
qs(st, j);
if(i < dr)
qs(i, dr);
}
int main(){
srand(time(NULL));
in = fopen("hvrays.in", "r");
FILE *out = fopen("hvrays.out", "w");
int t, h, v, i, l, hmcrt, hmpsb, rez;
t = getnum();
for(; t > 0; t--){
h = getnum();
v = getnum();
for(i = 0; i < h; i++){
x[i] = getnum();
y[i] = getnum();
tip[i] = 0;
point[i] = i;
}
for(i = 0; i < v; i++){
x[i + h] = getnum();
y[i + h] = getnum();
tip[i + h] = 1;
point[i + h] = i + h;
}
l = h + v;
qs(0, l - 1);
rez = 0;
hmcrt = hmpsb = -1;
for(i = 0; i < l; i++){
if(tip[point[i]] == 1 && hmpsb < y[point[i]])
hmpsb = y[point[i]];
if(tip[point[i]] == 0 && y[point[i]] > hmcrt){
hmcrt = hmpsb;
rez++;
}
}
fprintf(out, "%d\n", rez);
}
fclose(in);
fclose(out);
return 0;
}