HDU-4698 Counting
题意：给定一个二维平面，其中x取值为1-N，y取值为1-M，现给定K个点，问至少包括K个点中的一个的满足要求的<Xmin, Xmax, Ymin, Ymax>共有多少中取值情况。也就是说K个点中至少一个点落在所给定的区间内。
解法：正面求解，由于点只有1000个，因此直接暴力离散化之后的x轴坐标，对于y轴则可以通过增加一个一个加入点，使用一个set来维护纵轴有多少种不同的取法。
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <set>
using namespace std; typedef long long LL;
const int N = ;
const int mod = int(1e9)+;
const int inf = 0x7fffffff;
struct Point {
int x, y;
Point() {}
Point(int _x, int _y) : x(_x), y(_y) {}
bool operator < (const Point &t) const {
if (x != t.x) return x < t.x;
else return y < t.y;
}
}p[N];
int n, m, K;
int val[N];
set<int>st;
set<int>::iterator it1, it2; int main() {
while (scanf("%d %d %d", &n, &m, &K) != EOF) {
for (int i = ; i <= K; ++i) {
scanf("%d %d", &p[i].x, &p[i].y);
val[i] = p[i].x;
}
sort(p+, p+K+);
sort(val+, val++K);
int cnt = unique(val, val+K+)-val; // 去重之后的x轴坐标
val[] = ; val[cnt++] = n+;
LL ret = ;
for (int i = ; i < cnt-; ++i) {
st.clear(); st.insert(); st.insert(m+);
LL sum = ;
for (int j = i; j < cnt-; ++j) {
int left = lower_bound(p+, p++K, Point(val[j], ))-p;
int right = upper_bound(p+, p++K, Point(val[j], inf))-p;
for (int k = left; k < right; ++k) { // x轴取值为val[j]的点一次性取出来
if (st.count(p[k].y)) continue;
st.insert(p[k].y);
it1 = it2 = st.find(p[k].y);
it1--, it2++; // 找前一个和后一个
sum = (sum+1LL*(p[k].y-*(it1))*(*(it2)-p[k].y)%mod)%mod; // 新增加的y值对，统计只跨过该点的
}
ret = (ret+sum*(val[i]-val[i-])%mod*(val[j+]-val[j])%mod)%mod
}
}
printf("%I64d\n", ret);
}
return ;
}