JOI 村有一片荒地,上面竖着N个稻草人。任意两个稻草人的横坐标都不相同,任意两个稻草人的纵坐标都不相同。村民们每年多次在稻草人们的周围举行祭典。 有一次,JOI 村的村长听到了稻草人们的启示,计划在荒地中开垦一片田地。和启示中的一样,田地需要满足以下条件: 1.田地的形状是边平行于坐标轴的长方形; 2.左下角和右上角各有一个稻草人; 3.田地的内部(不包括边界)没有稻草人。 给出每个稻草人的坐标,请你求出有多少个满足条件的田地。 Input 第一行一个正整数N ,代表稻草人的个数。 接下来N行,第 i 行包含 2 个由空格分隔的整数X_i和Y_i,表示第i个稻草人的坐标。 Output 一行,一个整数,表示有多少个满足条件的田地。要求C++实现,且使用scanf函数,请给出具体代码
时间: 2023-06-17 22:07:03 浏览: 149
整人代码(太好玩了),用c++做的哦!
```c++
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 5005;
struct Point {
int x, y;
} a[MAXN];
int main() {
int n, ans = 0;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d%d", &a[i].x, &a[i].y);
}
sort(a + 1, a + n + 1, [](Point p1, Point p2) {
return p1.x < p2.x || (p1.x == p2.x && p1.y < p2.y);
}); // 按横坐标排序
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
int dx = a[j].x - a[i].x, dy = a[j].y - a[i].y;
if (i > 1 && dx > 0) break; // 优化1
if (j < n && dx < 0) continue; // 优化2
int cnt = 0;
for (int k = 1; k <= n; k++) {
if (a[k].x >= a[i].x && a[k].x <= a[j].x &&
a[k].y >= a[i].y && a[k].y <= a[j].y) {
cnt++;
}
}
if (cnt == n - 2) ans++; // 统计答案
}
}
printf("%d\n", ans);
return 0;
}
```
阅读全文