算法分析与设计作业1

记录

大二下课程繁重，尤其是算法分析与设计这门课难度更甚，特此记录。以便日后复习

题目要求

1．有一个水平放置的矩形纸箱，现希望用隔板把这个纸箱分割成很多小的格子，每个格子都可以放下若干个物品。从上往下看的效果如下图所示。已知纸箱左上角和右下角的坐标以及每个隔板放入纸箱后的位置坐标。现有若干个物品，已知物品放入纸箱后的位置，求每个格子中有多少个物品？

输入描述：

输入的第一行包含6个整数，分别是n（0<n<=5000），m(0<m<=5000)，x1，y1，x2，y2，分别表示隔板的数量，物品的数量，矩形纸箱左上角点的坐标和右下角点的坐标（从上往下看投影到XY平面的坐标），其后有n行，分别表示隔板的位置，按从左到右的顺序排列，且各个隔板互不相交。每一行有两个整数，Ui和Li，表示第i个隔板的位置坐标在（Ui,y1）和(Li,y2)。其后的m行，每一行有两个整数，Xj 和Yj，分别表示物品的位置。物品不可能正好在隔板上，也不可能在箱子外。

输出描述：

输出n+1行，每一行的形式为：k:h。其中k表示格子的编号，最左边的格子为0，依次递增，最右边的格子为n；h为第k个格子中物品的数量。

数据输入

5 6 0 10 60 0
3 1
4 3
6 8
10 10
15 30
1 5
2 1
2 8
5 5
40 10
7 9
样例输出：
0: 2
1: 1
2: 1
3: 1
4: 0
5: 1

程序代码

#define  _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define N 100
typedef double Element;
struct point {
	Element x;
	Element y;
};
struct Baffle {
	Element Ui;//记录挡板上端的x
	Element Li;//记录挡板下端的y
};
int FindSlope(struct point*temp,double x1,double y1,double x2,double y2);
int main(void) {
  
	int n, m,i,j;//分别代表隔板的数量，物品的数量
	struct point leftside, rightside;//定义左上角和右上角的坐标
	scanf("%d %d %lf %lf %lf %lf", &n, &m, &leftside.x,&leftside.y,&rightside.x,&rightside.y);
	struct Baffle* a = (struct Baffle*)malloc(sizeof(struct Baffle) * n);//记录挡板的坐标
	struct point* b = (struct point*)malloc(sizeof(point) * m);//记录物品的坐标
	int* num = (int*)malloc(sizeof(int) * (n + 1));//记录物品在不同格子中的数量
	memset(num, 0, sizeof(int)*(n+1));//给赋初值为0
	for (i = 0; i < n; i++) {//输入挡板的坐标
		scanf("%lf %lf", &a[i].Ui, &a[i].Li);//仅仅只需要输入上端和下端的x坐标即可
	}
	for ( i = 0; i < m; i++) {
		scanf("%lf %lf", &b[i].x, &b[i].y);//输入物品的x，y坐标
		if (b[i].y<=leftside.y && b[i].x>=leftside.x && b[i].x<=rightside.x && b[i].y>=rightside.y) continue;
		else break;
	}
	for ( i = 0; i <m; i++) {
		for ( j = 0; j < n; j++) {
			if (FindSlope(&b[i], a[j].Ui, leftside.y, a[j].Li, rightside.y)) {//判断样品是否在隔板j左边的区域内
				num[j]++;
				break;
			}
		}
		if(j==n)
		num[n]++;//j==n,在最后一个区域内
	}
	for (i = 0; i < n + 1; i++) {
		printf("%d: %d\n", i, num[i]);//输出每个区域中物品的个数
	}
	system("pause");
	return 0;
}
int FindSlope(struct point* temp, double x1, double y1, double x2, double y2) {
	double k = (y1 - y2) / (x1 - x2);//求出直线的斜率
	double x = (y1 - temp->y) / k + temp->x;//求出该点与箱子上边界的交点的x坐标
	if (x < x1) return 1;
	else return 0;
}

测试截屏

流程图