首页 > ACM题库 > HDU-杭电 > Hdu 1859 最小长方形[解题报告] C++
2013
12-23

Hdu 1859 最小长方形[解题报告] C++

最小长方形

问题描述 :

给定一系列2维平面点的坐标(x, y),其中x和y均为整数,要求用一个最小的长方形框将所有点框在内。长方形框的边分别平行于x和y坐标轴,点落在边上也算是被框在内。

输入:

测试输入包含若干测试用例,每个测试用例由一系列坐标组成,每对坐标占一行,其中|x|和|y|小于 231;一对0 坐标标志着一个测试用例的结束。注意(0, 0)不作为任何一个测试用例里面的点。一个没有点的测试用例标志着整个输入的结束。

输出:

对每个测试用例,在1行内输出2对整数,其间用一个空格隔开。第1对整数是长方形框左下角的坐标,第2对整数是长方形框右上角的坐标。

样例输入:

12 56
23 56
13 10
0 0
12 34
0 0
0 0

样例输出:

12 10 23 56
12 34 12 34


分析:寻找数据中横纵坐标的极值,输出即可。刚开始没有想明白,用了结构体,准备用qsort排序,懒得改了。。
代码如下:

#include<stdio.h>
struct pp
{
 int x;
 int y;
};
pp ans[1000];
int main()
{
 int i,j;
 int count;
 int max_x,max_y,min_x,min_y;
 bool flag;
 while(scanf("%d%d",&ans[0].x,&ans[0].y)&&(ans[0].x||ans[0].y))
 {
  flag=0;
  min_x=max_x=ans[0].x;
  min_y=max_y=ans[0].y;
   count=1;
S1:  while(scanf("%d%d",&ans[1].x,&ans[1].y))
     {
       if(ans[1].x==0&&ans[1].y==0) {flag=1;break;}
    if(ans[1].x>max_x)  max_x=ans[1].x;
    if(ans[1].x<min_x)  min_x=ans[1].x;
    if(ans[1].y>max_y)  max_y=ans[1].y;
    if(ans[1].y<min_y)  min_y=ans[1].y;
     }
     if(flag==0) goto S1;
     else
     printf("%d %d %d %d\n",min_x,min_y,max_x,max_y);
 }
 return 0;
}

 


  1. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。

  2. /*
    * =====================================================================================
    *
    * Filename: 1366.cc
    *
    * Description:
    *
    * Version: 1.0
    * Created: 2014年01月06日 14时52分14秒
    * Revision: none
    * Compiler: gcc
    *
    * Author: Wenxian Ni (Hello World~), [email protected]
    * Organization: AMS/ICT
    *
    * =====================================================================================
    */

    #include
    #include

    using namespace std;

    int main()
    {
    stack st;
    int n,i,j;
    int test;
    int a[100001];
    int b[100001];
    while(cin>>n)
    {
    for(i=1;i>a[i];
    for(i=1;i>b[i];
    //st.clear();
    while(!st.empty())
    st.pop();
    i = 1;
    j = 1;

    while(in)
    break;
    }
    while(!st.empty()&&st.top()==b[j])
    {
    st.pop();
    j++;
    }
    }
    if(st.empty())
    cout<<"YES"<<endl;
    else
    cout<<"NO"<<endl;
    }
    return 0;
    }

  3. 站长,你好!
    你创办的的网站非常好,为我们学习算法练习编程提供了一个很好的平台,我想给你提个小建议,就是要能把每道题目的难度标出来就好了,这样我们学习起来会有一个循序渐进的过程!