Cod sursa(job #223570)

Utilizator mihai_floreaFlorea Mihai Alexandru mihai_florea Data 28 noiembrie 2008 20:50:55
Problema Hvrays Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <fstream>
#include <algorithm>
using namespace std;
const int NMAX=100001,Inf=66666666;
#define x first
#define y second
pair<int,int> h[NMAX],v[NMAX];
int T,H,V;
ifstream f("hvrays.in");
ofstream g("hvrays.out");
int p,u;
pair<int,int> q[NMAX];
void add(pair<int,int> P){
     while (u>=0 && q[u].y<=P.y) u--;
     q[++u]=P;
     }
int solve(){
    int i,j=1,sol=0,ymax;
    bool sw;
    sort(h+1,h+H+1);
    sort(v+1,v+V+1);
    add(make_pair(0,Inf));
    for (i=1;i<=V;++i){
     ymax=q[p].y;
     for (sw=false;h[j].x<=v[i].x;++j)
      if (h[j].y<=v[i].y) sw=true,add(h[j]);
     if (sw && v[i].y<ymax) ++sol;
     while (p<u && q[p].y>v[i].y) ++p;
     }
    return sol;
    }
int main(){
    int i;
    for (f>>T;T;T--){
        f>>H>>V;
        for (i=1;i<=H;++i) f>>h[i].x>>h[i].y;
        for (i=1;i<=V;++i) f>>v[i].x>>v[i].y;
        g<<solve()<<'\n';
        }
    return 0;
}