细微包围矩形

题材内容:

细微包围矩形。题材内容:

P1003 铺地毯

洛谷——P1003 铺地毯

给定一组二维坐标,表示直角坐标系内的3个多边形的总是的顶点的坐标体系。总计能包围那么些多边形的平行于坐标轴的微小矩形,输出它的左下角和右上角的坐标。

给定1组二维坐标,表示直角坐标系内的三个多边形的两次三番的极限的坐标种类。总括能包围这些多边形的平行于坐标轴的不大矩形,输出它的左下角和右上角的坐标。

题材叙述

为了准备3个奇特的颁奖典礼,协会者在会场的一片矩形区域(可看做是平面直角坐标系的率先象限)铺上①些矩形地毯。一共有
n 张地毯,编号从 壹 到n
。未来将那么些地毯依照号码从小到大的依次平行于坐标轴先后铺设,后铺的地毯覆盖在前方已经铺好的地毯之上。

地毯铺设达成后,协会者想通晓覆盖地面某些点的最下面的那张地毯的号子。注意:在矩形地毯边界和三个极端上的点也算被地毯覆盖。

难题叙述

美高梅开户网址,为了未焚徙薪三个特种的颁奖庆典,组织者在会场的一片矩形区域(可看作是平面直角坐标系的首先象限)铺上一些矩形地毯。一共有
n 张地毯,编号从 1 到n
。未来将这一个地毯根据号码从小到大的依次平行于坐标轴先后铺设,后铺的地毯覆盖在近年来早已铺好的地毯之上。

地毯铺设达成后,组织者想清楚覆盖地面有个别点的最上边包车型客车那张地毯的号码。注意:在矩形地毯边界和三个极点上的点也算被地毯覆盖。

 

输入格式:

输入输出格式

输入格式:

 

输入文件名字为carpet.in 。

输入共n+2 行。

首先行,一个整数n ,表示总共有 n 张地毯。

接下去的n 行中,第 i+一 行表示编号i 的地毯的音信,包蕴多少个正整数 a ,b
,g ,k
,每七个整数之间用五个空格隔离,分别表示铺设地毯的左下角的坐标(a ,b
)以及地毯在x轴和y 轴方向的长度。

第n+二 行包含五个正整数 x 和y,表示所求的地头的点的坐标(x ,y)。

 

出口格式:

 

出口文件名称叫carpet.out 。

出口共一 行,三个整数,表示所求的地毯的编号;若此处未有被地毯覆盖则输出-一。

 

输入输出格式

输入格式:

 

输入文件名称叫carpet.in 。

输入共n+2 行。

先是行,一个平头n ,表示总共有 n 张地毯。

接下去的n 行中,第 i+一 行表示编号i 的地毯的音信,包括八个正整数 a ,b
,g ,k
,每四个整数之间用二个空格隔离,分别代表铺设地毯的左下角的坐标(a ,b
)以及地毯在x轴和y 轴方向的尺寸。

第n+2 行包含四个正整数 x 和y,表示所求的地头的点的坐标(x ,y)。

 

输出格式:

 

输出文件名称为carpet.out 。

输出共壹 行,一个平头,表示所求的地毯的数码;若此处没有被地毯覆盖则输出-一。

 

输入格式:

先是行是3个正整数n表示顶点的数目,第壹行是n组整数,依次表示每种终端坐标的x和y值。

输入输出样例

输入样例#1:

3
1 0 2 3
0 2 3 3
2 1 3 3
2 2

出口样例#1:

3

输入样例#2:

3
1 0 2 3
0 2 3 3
2 1 3 3
4 5

输出样例#2:

-1

输入输出样例

输入样例#1:

3
1 0 2 3
0 2 3 3
2 1 3 3
2 2

输出样例#1:

3

输入样例#2:

3
1 0 2 3
0 2 3 3
2 1 3 3
4 5

出口样例#2:

-1

率先行是一个正整数n表示顶点的多寡,第二行是n组整数,依次表示各类终端坐标的x和y值。

输出格式:

说明

【样例解释1】

如下图,壹 号地毯用实线表示,二 号地毯用虚线表示,三号用双实线表示,覆盖点(贰,2)的最上边一张地毯是 三 号地毯。

美高梅开户网址 1

【数据范围】

对于30% 的数据,有 n ≤2 ;

对于50% 的数据,0 ≤a, b, g, k≤100;

对于100%的数据,有 0 ≤n ≤10,000 ,0≤a, b, g, k ≤100,000。

noip2011提高组day1第1题

 1 #include<cstdio>
 2 
 3 struct car{
 4     int x,y,lx,ly;
 5 }t[10010];
 6 int n,qx,qy;
 7 int main()
 8 {
 9     scanf("%d",&n);
10     for(int i=1;i<=n;++i)
11         scanf("%d%d%d%d",&t[i].x,&t[i].y,&t[i].lx,&t[i].ly);
12     scanf("%d%d",&qx,&qy);
13     for(int i=n;i;--i)
14     {
15         if(qx>=t[i].x && qx<=t[i].x+t[i].lx && qy>=t[i].y && qy<=t[i].y+t[i].ly)
16         {
17             printf("%d",i);
18             return 0;
19         }
20     }
21     printf("-1");
22     return 0;
23 }

 

说明

【样例解释一】

正如图,1 号地毯用实线表示,贰 号地毯用虚线表示,3号用双实线表示,覆盖点(贰,2)的最下边一张地毯是 三 号地毯。

美高梅开户网址 2

【数据范围】

对于30% 的数据,有 n ≤2 ;

对于50% 的数据,0 ≤a, b, g, k≤100;

对于100%的数据,有 0 ≤n ≤10,000 ,0≤a, b, g, k ≤100,000。

noip2011提高组day1第1题

 

本人壹上来就用的强力算法做的,三从循环,让每1次出席三个地毯现在就修改3回,然后,光荣的种种RE,MLE,TLE。

事实上对于她的那些坐标我依然挺纳闷的,为何坐标都要加,而且他说她提交的是做左下角的坐标,那样的话应该是减啊???

还要他以此地点所说的x,y坐标并不是与大家数学上所说的x,y坐标一样,他那么些地方的x竟然是竖着的!!!

美高梅开户网址 3数组开小的结果。。。

美高梅开户网址 4直白暴力+横纵坐标弄反的的结果。。。

美高梅开户网址 5一贯暴力。。。。

总的看咱们要找1个好点的做法,让大家不MLE。。。。

咱俩看清1个点被哪个人覆盖的时候,大家能够如此想:对于一块地毯当他的横纵坐标都低于所求点的横纵坐标&&它的横纵坐标都包含在地毯的横纵坐标+地毯的长度宽度之内,他就被那块地毯覆盖了,那样我们就足以用壹重循环求出那么些点被什么人覆盖了。。。

 

美高梅开户网址 6横纵坐标弄反。。。。

美高梅开户网址 7追根究底对了。。。。

 

 

 

 

代码:

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 100001
using namespace std;
int n,x[N],y[N],a[N],b[N],ans,xx,yy;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
     scanf("%d%d%d%d",&a[i],&b[i],&x[i],&y[i]);
    scanf("%d%d",&xx,&yy);
    for(int i=1;i<=n;i++)
     {
         if(a[i]+x[i]>=xx&&a[i]<=xx&&b[i]<=yy&&b[i]+y[i]>=yy)
           ans=i;
     }
    if(ans==0)     printf("-1");
    else printf("%d",ans);
    return 0;
}

 

 

多少个整数,依次表示所总结的矩形的左下角的坐标的x、y值和右上角坐标的x、y值。输出最终带有回车换行。

输出格式:

输入样例:

五个整数,依次表示所总括的矩形的左下角的坐标的x、y值和右上角坐标的x、y值。输出最后带有回车换行。

5

 

1 1 1 4 3 7 4 4 4 1

输入样例:

出口样例:

5

1 1 4 7

1 1 1 4 3 7 4 4 4 1

 1 #include <stdio.h> 2  3 typedef struct _dot { 4     int x; 5     int y; 6 } Dot; 7  8 int main(int argc, char const *argv[]) 9 {10     Dot left_down, right_up;11     left_down = right_up = {0,0};12 13     Dot p;14     int n;15     scanf("%d", &n);16 17     for ( int i = 0; i < n; i++ ) {18         scanf("%d %d", &p.x, &p.y);19         if ( left_down.x || left_down.y || right_up.x  || right_up.y ) {    20             if ( p.x < left_down.x ) {21                 left_down.x = p.x;22             } else if ( p.x > right_up.x ) {23                 right_up.x = p.x;24             }25             if ( p.y < left_down.y ) {26                 left_down.y = p.y;27             } else if ( p.y > right_up.y ) {28                 right_up.y = p.y;29             }30         } else {31             left_down = p;32             right_up = p;33         }34     }35     printf("%d %d %d %d\n", left_down.x, left_down.y, right_up.x, right_up.y);36     return 0;37 }

 

出口样例:

1 1 4 7

 1 #include <stdio.h>
 2 
 3 typedef struct _dot {
 4     int x;
 5     int y;
 6 } Dot;
 7 
 8 int main(int argc, char const *argv[])
 9 {
10     Dot left_down, right_up;
11     left_down = right_up = (Dot){0,0};
12 
13     Dot p;
14     int n;
15     scanf("%d", &n);
16 
17     for ( int i = 0; i < n; i++ ) {
18         scanf("%d %d", &p.x, &p.y);
19         if ( left_down.x || left_down.y || right_up.x  || right_up.y ) {    
20             if ( p.x < left_down.x ) {
21                 left_down.x = p.x;
22             } else if ( p.x > right_up.x ) {
23                 right_up.x = p.x;
24             }
25             if ( p.y < left_down.y ) {
26                 left_down.y = p.y;
27             } else if ( p.y > right_up.y ) {
28                 right_up.y = p.y;
29             }
30         } else {
31             left_down = p;
32             right_up = p;
33         }
34     }
35     printf("%d %d %d %d\n", left_down.x, left_down.y, right_up.x, right_up.y);
36     return 0;
37 }

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图