微小包围矩形

题材内容:

难题内容:

P1003 铺地毯

洛谷——P1003 铺地毯

给定一组二维坐标,表示直角坐标系内的四个多边形的连年的终极的坐标系列。总结能包围这一个多边形的平行于坐标轴的小不点儿矩形,输出它的左下角和右上角的坐标。

给定壹组二维坐标,表示直角坐标系内的二个多边形的总是的终点的坐标类别。总结能包围那几个多边形的平行于坐标轴的矮小矩形,输出它的左下角和右上角的坐标。

难题叙述

为了准备三个特种的颁奖典礼,组织者在会场的一片矩形区域(可看作是平面直角坐标系的第2象限)铺上一些矩形地毯。壹共有
n 张地毯,编号从 一 到n
。现在将那几个地毯依据号码从小到大的相继平行于坐标轴先后铺设,后铺的地毯覆盖在前面已经铺好的地毯之上。

地毯铺设完成后,协会者想驾驭覆盖地面有个别点的最上边的那张地毯的号码。注意:在矩形地毯边界和多少个极点上的点也算被地毯覆盖。

题材叙述

为了绸缪未雨3个非同小可的颁奖典礼,组织者在会场的一片矩形区域(可作为是平面直角坐标系的率先象限)铺上一些矩形地毯。壹共有
n 张地毯,编号从 一 到n
。以往将那些地毯依照号码从小到大的次第平行于坐标轴先后铺设,后铺的地毯覆盖在前头早已铺好的地毯之上。

地毯铺设达成后,协会者想通晓覆盖地面有些点的最上边的那张地毯的数码。注意:在矩形地毯边界和多个终端上的点也算被地毯覆盖。

 

输入格式:

输入输出格式

输入格式:

 

输入文件名叫carpet.in 。

输入共n+2 行。

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

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

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

 

输出格式:

 

出口文件名字为carpet.out 。

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

 

输入输出格式

输入格式:

 

输入文件名叫carpet.in 。

微小包围矩形。输入共n+2 行。

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

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

第n+二 行包括三个正整数 x 和y,表示所求的本土的点的坐标(x ,y)。

 

输出格式:

 

出口文件名称叫carpet.out 。

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

 

输入格式:

第三行是贰个正整数n表示顶点的数码,第1行是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值。

输出格式:

说明

【样例解释一】

正如图,壹 号地毯用实线表示,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 }

 

说明

【样例解释1】

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

亚洲必赢官网 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题

 

自作者壹上来就用的强力算法做的,3从循环,让每二回加入1个地毯以往就修改3回,然后,光荣的各类RE,MLE,TLE。

实在对于他的这几个坐标笔者依然挺纳闷的,为啥坐标都要加,而且她说她付出的是做左下角的坐标,那样的话应该是减啊???

而且他这几个地方所说的x,y坐标并不是与大家数学上所说的x,y坐标一样,他这几个地方的x竟然是竖着的!!!

亚洲必赢官网 3数组开小的后果。。。

亚洲必赢官网 4直接暴力+横纵坐标弄反的的结果。。。

亚洲必赢官网 5直白暴力。。。。

因而看来大家要找2个好点的做法,让我们不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地图