MRECT1 - Điểm trên cạnh hình chữ nhật - HRASTOVI

Tác giả: skyvn97

Ngôn ngữ: C++

#include<bits/stdc++.h>
#define MAXP   300300
#define MAXR   100100
#define x   first
#define y   second
using namespace std;
typedef pair<int,int> point;
point ax[MAXP];
point ay[MAXP];
int n,p;
bool cmpx(const point &a,const point &b) {
	if (a.x<b.x) return (true);
	if (a.x>b.x) return (false);
	return (a.y<b.y);
}
bool cmpy(const point &a,const point &b) {
	if (a.y<b.y) return (true);
	if (a.y>b.y) return (false);
	return (a.x<b.x);
}
void init(void) {
	int i,px,py;
	scanf("%d",&n);
	for (i=1;i<=n;i=i+1) {
		scanf("%d",&px);
		scanf("%d",&py);
		ax[i]=point(px,py);
		ay[i]=point(px,py);	
	}	
	sort(&ax[1],&ax[n+1],cmpx);
	sort(&ay[1],&ay[n+1],cmpy);
}
int county(const int &y,const int &x1,const int &x2) {	
	if (x1>x2) return (0);
	if (cmpy(ay[n],point(x1,y))) return (0);
	if (cmpy(point(x2,y),ay[1])) return (0);
	int f,l;
	f=lower_bound(&ay[1],&ay[n+1],point(x1,y),cmpy)-&ay[0];	
	if (cmpy(point(x2,y),ay[n])) l=upper_bound(&ay[1],&ay[n+1],point(x2,y),cmpy)-&ay[0];
	else l=n+1;
	return (l-f);
}
int countx(const int &x,const int &y1,const int &y2) {
	if (y1>y2) return (0);
	if (cmpx(ax[n],point(x,y1))) return (0);
	if (cmpx(point(x,y2),ax[1])) return (0);
	int f,l;
	f=lower_bound(&ax[1],&ax[n+1],point(x,y1),cmpx)-&ax[0];
	if (cmpx(point(x,y2),ax[n])) l=upper_bound(&ax[1],&ax[n+1],point(x,y2),cmpx)-&ax[0];
	else l=n+1;
	return (l-f);
}
void process(void) {
	int i,r,x1,y1,x2,y2;
	scanf("%d",&p);
	for (i=1;i<=p;i=i+1) {
		r=0;
		scanf("%d",&x1);
		scanf("%d",&y1);
		scanf("%d",&x2);
		scanf("%d",&y2);	
		r+=county(y1,x1,x2);
		r+=county(y2,x1,x2);
		r+=countx(x1,y1+1,y2-1);
		r+=countx(x2,y1+1,y2-1);
		printf("%d\n",r);
	}
}
int main(void) {
	init();
	process();
	return 0;
}

Download