最小包围矩形

主题材料内容:

P1003 铺地毯

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

难点陈述

为了未雨盘算粮草先行二个奇特的颁奖仪式,组织者在会议室的一片矩形区域(可看作是平面直角坐标系的首先象限)铺上一些矩形地毯。生龙活虎共有 n 张地毯,编号从 1 到n 。现在将这几个地毯根据号码从小到大的生龙活虎生龙活虎平行于坐标轴前后相继铺设,后铺的地毯覆盖在前头早就铺好的地毯之上。

地毯铺设完毕后,组织者想驾驭覆盖地面有个别点的最上面的那张地毯的编号。注意:在矩形地毯边界和多个顶峰上的点也算被地毯覆盖。

 

输入输出格式

输入格式:

 

输入文件名字为carpet.in 。

输入共n 2 行。

第朝气蓬勃行,二个平头n ,表示总共有 n 张地毯。

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

第n 2 行蕴涵五个正整数 x 和y,表示所求的地头的点的坐标(x ,y)。

 

输出格式:

 

输出文件名称为carpet.out 。

出口共1 行,二个卡尺头,表示所求的地毯的数码;若此处未有被地毯覆盖则输出-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】

常常来说图,1 号地毯用实线表示,2 号地毯用虚线表示,3 号用双实线表示,覆盖点(2,2)的最上边一张地毯是 3 号地毯。

图片 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 }

 

 

出口格式:

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

 

输入样例:

5

1 1 1 4 3 7 4 4 4 1

 

输出样例:

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 %dn", left_down.x, left_down.y, right_up.x, right_up.y);
36     return 0;
37 }

 

本文由星彩网app下载发布于计算机编程,转载请注明出处:最小包围矩形

TAG标签: 星彩网app下载
Ctrl+D 将本页面保存为书签,全面了解最新资讯,方便快捷。