威尼斯人线上娱乐

细微包围矩形

11 4月 , 2019  

难点内容:

题材内容:

P1003 铺地毯

洛谷——P1003 铺地毯

威尼斯人线上娱乐 ,给定一组2维坐标,表示直角坐标系内的贰个多边形的连年的终点的坐标体系。总计能包围那个多边形的平行于坐标轴的纤维矩形,输出它的左下角和右上角的坐标。

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

题材叙述

为了准备三个异样的颁奖典礼,组织者在会场的一片矩形区域(可作为是平面直角坐标系的率先象限)铺上1些矩形地毯。壹共有
n 张地毯,编号从 壹 到n
。以往将这么些地毯根据号码从小到大的相继平行于坐标轴先后铺设,后铺的地毯覆盖在前面早已铺好的地毯之上。

地毯铺设达成后,协会者想知道覆盖地面有个别点的最下面的那张地毯的号子。注意:在矩形地毯边界和两极分化上的点也算被地毯覆盖。

难点叙述

为了未焚徙薪1个特出的颁奖典礼,协会者在会场的一片矩形区域(可视作是平面直角坐标系的首先象限)铺上一些矩形地毯。一共有
n 张地毯,编号从 1 到n
。以后将这几个地毯遵照号码从小到大的相继平行于坐标轴先后铺设,后铺的地毯覆盖在前方已经铺好的地毯之上。

地毯铺设实现后,组织者想掌握覆盖地面某些点的最上边包车型地铁那张地毯的号码。注意:在矩形地毯边界和八个极点上的点也算被地毯覆盖。

 

输入格式:

输入输出格式

输入格式:

 

输入文件名字为carpet.in 。

输入共n+2 行。

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

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

第n+二 行李包裹括多少个正整数 x 和y,表示所求的本地的点的坐标(x ,y)。

 

输出格式:

 

细微包围矩形。输出文件名叫carpet.out 。

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

 

输入输出格式

输入格式:

 

输入文件名叫carpet.in 。

输入共n+2 行。

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

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

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

 

输出格式:

 

出口文件名称为carpet.out 。

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

 

输入格式:

率先行是1个正整数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

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

输出格式:

说明

【样例解释1】

正如图,壹 号地毯用实线表示,二 号地毯用虚线表示,三号用双实线表示,覆盖点(2,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 }

 

说明

【样例解释一】

正如图,壹 号地毯用实线表示,贰 号地毯用虚线表示,三号用双实线表示,覆盖点(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上来就用的强力算法做的,三从循环,让每二次投入二个地毯今后就修改三遍,然后,光荣的种种RE,MLE,TLE。

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

再者她以此地点所说的x,y坐标并不是与大家数学上所说的x,y坐标壹样,他以此地点的x竟然是竖着的!!!

威尼斯人线上娱乐 3数组开小的结果。。。

威尼斯人线上娱乐 4直白暴力+横纵坐标弄反的的结果。。。

威尼斯人线上娱乐 5直白暴力。。。。

由此看来大家要找一个好点的做法,让大家不MLE。。。。

大家判断1个点被哪个人覆盖的时候,大家得以这么想:对于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地图