大家好,又见面了,我是你们的朋友全栈君。
题目描述
输入描述:
第一行,一个整数n,表示总共有n张地毯。
接下来的n行中,第i+1行表示编号i的地毯的信息,包含四个正整数a,b,g,k,每两个整数之间用一个空格隔开,分别表示铺设地毯的左下角的坐标(a,b)以及地毯在x轴和y轴方向的长度。
第n+2行包含两个正整数x和y,表示所求的地面的点的坐标(x,y)。
输出描述:
输出共1行,一个整数,表示所求的地毯的编号;若此处没有被地毯覆盖则输出-1。
备注:
对于30%的数据,有n≤2;
对于50%的数据,有0≤a,b,g,k≤100;
对于100%的数据,有0≤n≤10,000,0≤a,b,g,k≤100,000。
#include<iostream> using namespace std; int main() { int n; int i; cin>>n; int x,y,a,b; int map[10000][4]; for(i=0;i<n;i++) { cin>>x>>y>>a>>b; map[i][0] = x; map[i][1] = y; map[i][2] = x+a; map[i][3] = y+b; } int c,d; int flag=-1; cin>>c>>d; for(i=0;i<n;i++) { if(map[i][0]<=c&&map[i][1]<=d&&map[i][2]>=c&&map[i][3]>=d) { flag = i; } } if(flag == -1) cout<<-1; else cout<<flag+1; }
总结:
这题要用逆向思维,不是先根据地毯算出每一个点的情况,而是对每个输入的点找有多少地毯覆盖在这个点上,这样大大减少了空间的浪费
具体的直接找到对角线的两个点的坐标,然后看输入的点的坐标是否在这两个点之间即可
转载于:https://www.cnblogs.com/miliye/p/10199475.html
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/107109.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...