ACM练习 校赛83C:纸片儿(测试用例通过但WA/TLE)

描述

S 君喜欢用大头针儿扎纸片儿玩儿。

输入
第一行为一个整数 n (0 <= n <= 100)，表示纸片的个数
之后的 n 行中，第 i 行为四个整数 Ai, Bi, Ci, Di (-1000000000 <= Ai < Ci <= 1000000000; -1000000000 <= Bi < Di <= 1000000000)，分别表示第 i 个纸片（可以视为和坐标轴对齐的矩形）左下角坐标 (Ai, Bi) 和右上角坐标 (Ci, Di)。

输出
S 君一个大头针儿下去最多能扎到多少个纸片儿？

假设大头针可以穿透任意数量的纸片；
若大头针刚好沿着纸片的边缘穿过，则不计入该纸片；
大头针的坐标可以取任意实数。

样例输入
4
0 0 1 1
1 0 2 1
2 0 3 1
0 0 3 1

样例输出
2

我的测试用例

4
0 0 3 1
0 0 3 1
0 0 3 1
0 0 3 1
答案：4

3
0 0 2 2
1 1 3 3
2 2 4 4
答案：2

4
0 0 2 2
1 1 3 3
2 2 4 4
2 0 5 5
答案：3

5
0 0 2 2
1 1 3 3
2 2 4 4
2 0 5 5
0 3 2 5
答案：3

7
0 0 2 2
1 1 3 3
2 2 4 4
2 0 5 5
0 3 2 5
0 0 5 5
0 0 5 5
答案：5

代码

思路：先找到一个能包括左所有纸片的最小范围D，然后以0.5单位一次的步伐，遍历D中的每个位置，计算这些位置的厚度，找出最大厚度。

#include<iostream> using namespace std; class Paper { public:int left;int right;int up;int down; };int main() {int leftmin = 1000000000, rightmax = -1000000000, upmax = -1000000000, downmin = 1000000000;int total;cin >> total;int i;Paper paper[100];//找到边缘,这个最厚的点在边缘之内for (i = 0; i < total; i++){cin >> paper[i].left >> paper[i].down >> paper[i].right >> paper[i].up;if (paper[i].left < leftmin)leftmin = paper[i].left;if (paper[i].right > rightmax)rightmax = paper[i].right;if (paper[i].up > upmax)upmax = paper[i].up;if (paper[i].down < downmin)downmin = paper[i].down;}//遍历边缘之内所有的点(left,up)(right,up);(left,down),(right,down)double x, y;int paperOKmax = 0;int paperOK = 0;for (x = leftmin; x <= rightmax; x += 0.5){for (y = downmin; y <= upmax; y += 0.5){if (paperOK > paperOKmax)paperOKmax = paperOK;paperOK = 0;for (i = 0; i < total; i++){if (paper[i].left < x && paper[i].right > x && paper[i].up > y && paper[i].down < y){paperOK++;}}}}cout << paperOKmax;cout << endl;system("pause"); }

总结

以上是生活随笔为你收集整理的ACM练习 校赛83C:纸片儿(测试用例通过但WA/TLE)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。