NOIP2011提高组铺地毯题解

题解又双叒叕来了!

NOIP2011提高组铺地毯题解

 

 最开始,我很傻的以为,要把每一块地毯铺的位置,模拟出来。
 也就是听着题目的话,从第1张地毯到第n张地毯都“铺”在一个二维数
 组里,当然,如果这么做,好像有(hui)点(chang)麻烦。
 经过本懒货“绞尽脑汁”思考了非(liang)常(fen)久
  (zhong),偶灵光一现,我发现:
 其实我们可以从第1张地毯到第n张地毯判断,地毯所铺的范围里有没有
(x,y)坐标,有的话,当前最上面一层就标记为当前地毯,这样就很
  简单啦

NOIP2011提高组铺地毯题解

看到这道题先理解清楚题意:

就是给n张地毯的信息,信息包括左下角点的横纵坐标,

然后他向上和向左的扩展方向,其实给出这几个信息就足以概括出整个地毯了,

再随便给的一个点与上左扩展方向就出现了个大体,我们把它画完整就是个地毯了。

然后再给你一个点让你看看点包不包括在给出的这n个地毯内,在就输出那个包括它的最新的地毯号,没有就输出-1;

其实分析完题目许多朋友也觉得并

不难,的确这道题并不难,

NOIP2011提高组铺地毯题解

主要就是如何判断点是否包括在一个矩形内,

那么如何判断呢?我们就来看看一个点再一个矩形内有哪些特征?

一个点是否在一个矩形内部我们不难发现,那个点必须在最下面一条边的上面但不能超过左边一条边的边长,

这个点必须在左边边的右侧但不能超过底边的边长;

没错就是一句话的事,设此点坐标为x,y,地毯数据是a[10001],b[10001],g[10001],k[10001];
那么公式就是 x>=a[i]&&x<=a[i]+g[i]&&y>=b[i]&&y<=b[i]+k[i];

上代码

#include<iostream>
#include<cstdio>
#include<cmath>
#include<queue>
#include<cstring>
using namespace std;
int a[100010][5]; 
int main()
{ 
 int n,x,y;
 cin>>n;
 for(int i=1;i<=n;i++)
 {
  for(int j=1;j<=4;j++) cin>>a[i][j];
  } 
  cin>>x>>y;
  for(int i=n;i>=1;i--)
  {
   if((a[i][1]<=x)&&(a[i][3]+a[i][1]>=x)&&(a[i][2]<=y)&&(a[i][4]+a[i][2]>=y))
   {
    cout<<i<<endl;
    break;
   }
   if(i==1)
   {
    cout<<-1<<endl;
    break;
   }
  }
 return 0;
}//华丽结束

 

这道题结束了,你学废了吗?

学废了扣1,没学废扣眼珠子

最后,恳请大家

NOIP2011提高组铺地毯题解

 

上一篇:NOIP2011 [提高组] 观光公交


下一篇:[NOIP2011]铺地毯(贪心)