code+3月赛 loj6299 白金元首与克劳德斯

千里白金雪满天　烽火*起狼烟　分手竟兵刃相见

1941.7.

苏联军队出乎意料的反抗力量、前线德军的补给困难 —— 元首 Adolf 望着天空的云层陷入沉思……

在 $(xi,yi,wi,hi,di)(x_i, y_i, w_i, h_i, d_i)(xi,yi,wi,hi,di) 表示，其中 (xi,yi)(x_i, y_i)(xi,yi) 为云左下角顶点的坐标，wiw_iwi 表示云在 xxx 轴方向的宽度，hih_ihi 表示云在 yyy 轴方向的长度，di∈{0,1}d_i in {0, 1}di∈{0,1} 为云的移动方向（000 为横向，111 为纵向）。具体来说，满足 di=0d_i = 0di=0 的云沿 xxx 轴正方向以每秒 111 长度单位的速率不断移动，而满足 di=1d_i = 1di=1 的云沿 yyy 轴正方向以每秒 111 长度单位的速率不断移动。$

元首发现，所有的云在此时没有重叠的面积。他将这个时刻记作时刻

你需要编写程序帮助元首满足他的好奇心。

从标准输入读入数据。

输入的第一行包含一个正整数

第
接下来 $xix_ixi、yiy_iyi、wiw_iwi、hih_ihi 和 did_idi —— 描述一朵云在时刻 000 的状态。$

输出到标准输出。

对于每组数据输出一行 —— 在任意时刻，覆盖平面上任意一个点的云朵数目的最大值。

样例输入

3
1
0 0 1 1 0
3
0 -10 10 10 1
10 0 10 10 1
-10 0 10 10 0
3
0 10 10 10 1
10 20 10 10 1
10 0 10 10 0

样例输出

1
2
2

第

code+3月赛 loj6299 白金元首与克劳德斯

第

子任务

对于所有数据，有 $10^8 leq x_i, y_i leq -5 imes 10^8−5×108≤xi,yi≤−5×108，1≤wi,hi≤−5×1081 leq w_i, h_i leq -5 imes 10^81≤wi,hi≤−5×108，di∈{0,1}d_i in {0, 1}di∈{0,1}。$

测试点编号		特殊约定
1		无
2		无
3		$x_i, y_i leq 50−50≤xi,yi≤50，1≤wi,hi≤501 leq w_i, h_i leq 501≤wi,hi≤50$
4
5		$wi=hi=1w_i = h_i = 1wi=hi=1$
6		$−103≤xi,yi≤103-10^{3} leq x_i, y_i leq 10^{3}−103≤xi,yi≤103，1≤wi,hi≤1031 leq w_i, h_i leq 10^{3}1≤wi,hi≤103$
7
8		$wi=hi=1w_i = h_i = 1wi=hi=1$
9		$wi=hi=1w_i = h_i = 1wi=hi=1$
10		无

“Dann soll die Armee eben kehrt machen!”

题面与史实无关。

提示

最大输入约为 50 MiB，请注意程序在读入上的耗时哦。

来自 CodePlus 2017 3 月赛，清华大学计算机科学与技术系学生算法与竞赛协会荣誉出品。
Credit：idea/吕时清　命题/吕时清　验题/丁子钧
Git Repo：https://git.thusaac.org/publish/CodePlus3
感谢腾讯公司对此次比赛的支持。

题意：N个矩形的云，分两种，一种沿x轴正方向移动，一种沿y轴正方向移动，速度都为1

t=0时刻没有矩形相交，问在某个时间点最多有多少朵云重合（考虑 t 为负的情况）

分析：

思考可得，最多有两朵云相交，那么答案就只能是1或2

问题转化为判断会不会有两朵云在某个时刻相交

给出如下推导

问题最终转化为判断最后一行的式子是否对于每对移动方向不同的矩形都成立

其实就是N个区间是否有相交的两个区间。

可以二分，可以BIT，我用了set

 1 /*
 2 Welcome Hacking
 3 Wish You High Rating
 4 */
 5 #include<iostream>
 6 #include<cstdio>
 7 #include<cstring>
 8 #include<ctime>
 9 #include<cstdlib>
10 #include<algorithm>
11 #include<cmath>
12 #include<string>
13 #include<set>
14 using namespace std;
15 int read(){
16     int xx=0,ff=1;char ch=getchar();
17     while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
18     while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
19     return xx*ff;
20 }
21 int T,N;
22 struct cloud_{
23     int x,y,w,h,d;
24     bool friend operator<(const cloud_&A,const cloud_&B)
25     {return A.x+A.y<B.x+B.y;}
26 }C[100010];
27 set<cloud_>s;
28 int calc(){
29     s.clear();
30     for(int i=1;i<=N;i++)
31         if(!C[i].d)
32             s.insert(C[i]);
33     for(int i=1;i<=N;i++)
34         if(C[i].d){
35             set<cloud_>::iterator j=s.lower_bound(C[i]);
36             if(j!=s.end())
37                 if(C[i].x+C[i].y+C[i].w+C[i].h>j->x+j->y)
38                     return 2;
39         }
40     //两种相交的情况都要判断
41     s.clear();
42     for(int i=1;i<=N;i++)
43         if(C[i].d)
44             s.insert(C[i]);
45     for(int i=1;i<=N;i++)
46         if(!C[i].d){
47             set<cloud_>::iterator j=s.lower_bound(C[i]);
48             if(j!=s.end())
49                 if(C[i].x+C[i].y+C[i].w+C[i].h>j->x+j->y)
50                     return 2;
51         }
52     return 1;
53 }
54 int main(){
55     //freopen("in","r",stdin);
56     //freopen("out","w",stdout);
57     for(int T=read();T;T--){
58         N=read();
59         for(int i=1;i<=N;i++)
60             C[i].x=read(),C[i].y=read(),C[i].w=read(),C[i].h=read(),C[i].d=read();
61         sort(C+1,C+1+N);
62         printf("%d
",calc());
63     }
64     return 0;
65 }

View Code

code+3月赛 loj6299 白金元首与克劳德斯

输入格式

输出格式

样例

样例输入

样例输出

数据范围与提示

子任务

提示

code+3月赛 loj6299 白金元首与克劳德斯

输入格式

输出格式

样例

样例输入

样例输出

数据范围与提示

子任务

提示

相关推荐