鋪地毯

描述

為了準備一個獨特的頒獎典禮，組織者在會場的一片矩形區域（可看做是平面直角坐標系的第一象限）鋪上一些矩形地毯。一共有n張地毯，編號從1到n。現在將這些地毯按照編號從小到大的順序平行于坐標軸先后鋪設，后鋪的地毯覆蓋在前面已經鋪好的地毯之上。地毯鋪設完成后，組織者想知道覆蓋地面某個點的最上面的那張地毯的編號。注意：在矩形地毯邊界和四個頂點上的點也算被地毯覆蓋。

格式

輸入格式

輸入共n+2行。

第一行，一個整數n(0 <= n <= 10,000)，表示總共有n張地毯。

接下來的n行中，第i+1行表示編號i的地毯的信息，包含四個正整數a，b，g，k(0 <= a, b, g, k <= 100,000)，每兩個整數之間用一個空格隔開，分別表示鋪設地毯的左下角的坐標（a，b）以及地毯在x軸和y軸方向的長度。

第n+2行包含兩個正整數x和y，表示所求的地面的點的坐標（x，y）。

輸出格式

輸出共1行，一個整數，表示所求的地毯的編號；若此處沒有被地毯覆蓋則輸出-1。

樣例1

樣例輸入1

3 1 0 2 3 0 2 3 3 2 1 3 3 2 2

樣例輸出1

3

樣例2

樣例輸入2

3 1 0 2 3 0 2 3 3 2 1 3 3 4 5

樣例輸出2

-1

限制

1s

來源

NOIp2011提高組Day1第一題

題目鏈接：https://vijos.org/p/1736

分析：要找鋪在最上面的編號，實際上就是for去掃一遍，判斷點是否滿足條件在區域內的條件，滿足就將i的值賦給給ans，否則ans=-1；

下面給出AC代碼：

1 #include <bits/stdc++.h> 2 using namespace std; 3 const int N=100010; 4 int a[N],b[N],g[N],k[N]; 5 int n,x,y,ans=-1; 6 int main() 7 { 8 cin>>n; 9 for(int i=1;i<=n;i++) 10 cin>>a[i]>>b[i]>>g[i]>>k[i]; 11 cin>>x>>y; 12 for(int i=1;i<=n;i++) 13 { 14 if(x>=a[i]&&x<=a[i]+g[i]&&y>=b[i]&&y<=b[i]+k[i]) 15 ans=i; 16 } 17 cout<<ans<<endl; 18 return 0; 19 }

?

總結

以上是生活随笔為你收集整理的Vjios P1736 铺地毯【暴力，思维】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。