#include<iostream>
#include<cstdio>
#include<cstring>
#define maxa 10100
using namespace std;
struct Node
{
int x,y,s,t;
}e[maxa];
int main()
{
int p,q,i;
int n,a,b,g,k;
cin>>n;
for(i=1;i<=n;++i)
{
cin>>a>>b>>g>>k;
e[i].x = a;
e[i].y = b;
e[i].s = a+g;
e[i].t = b+k;
}
int x,y;
cin>>x>>y;
int t = 0;
for(i=1;i<=n;++i)
{
if((x>=e[i].x&&x<=e[i].s)&&(y>=e[i].y&&y<=e[i].t))
t = i;
}
if(t)
cout<<t<<endl;
else
cout<<-1<<endl;
return 0;
}

#include<iostream>
#include<cstdio>
#include<cstring>
#define maxa 10100
using namespace std;
struct Node
{
int x,y,s,t;
}e[maxa];
int main()
{
int p,q,i;
int n,a,b,g,k;
cin>>n;
for(i=1;i<=n;++i)
{
cin>>a>>b>>g>>k;
e[i].x = a;
e[i].y = b;
e[i].s = a+g;
e[i].t = b+k;
}
int x,y;
cin>>x>>y;
int t = 0;
for(i=1;i<=n;++i)
{
if((x>=e[i].x&&x<=e[i].s)&&(y>=e[i].y&&y<=e[i].t))
t = i;
}
if(t)
cout<<t<<endl;
else
cout<<-1<<endl;
return 0;
}

本来以为有什么优化的算法，看了一圈题解貌似就是考模拟？
#include <iostream>
#include <cstdio>
using namespace std;
const int MAXN=1e5+5;
int N,X,Y;
struct Node
{
int sx,sy,dx,dy;
Node(){}
Node(int ssx,int ssy,int ddx,int ddy)
{
sx=ssx;
sy=ssy;
dx=ddx;
dy=ddy;

}
}L[MAXN];
void Init()
{
int len=0;
int a,b,c,d;
for(int i=0;i<N;i++)
{
scanf("%d%d%d%d",&a,&b,&c,&d);
L[++len]=Node(a,b,c,d);
}
scanf("%d%d",&X,&Y);
}
bool inblock(int i)
{
if(L[i].sx<=X&&(L[i].dx+L[i].sx)>=X&&L[i].sy<=Y&&(L[i].sy+L[i].dy)>=Y)
return true;
return false;
}
void Solve()
{
for(int i=N;i>=0;i--)
{
if(i==0)
printf("-1\n");
if(inblock(i))
{

printf("%d\n",i);
break;
}
}
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
while(scanf("%d",&N)!=EOF)
{
Init();
Solve();
}
return 0;
}

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;

const int MAX=100000+34;

int n,m,pos=-1,x,y;

struct num
{
int minx,miny,maxx,maxy;
} N[MAX];

int main()
{
scanf("%d",&n);

int a,b,k,g;
for(int i=1;i<=n;i++)
{
cin>>a>>b>>k>>g;
N[i].minx=a;
N[i].miny=b;
N[i].maxx=a+k;
N[i].maxy=b+g;
}

scanf("%d%d",&x,&y);

for(int i=1;i<=n;i++)
if(x>=N[i].minx&&x<=N[i].maxx&&y>=N[i].miny&&y<=N[i].maxy)
pos=i;
cout<<pos;
return 0;
}

#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;

int x[100005], y[100005], w[100005], l[100005];

int main() {
int n;
scanf("%d", &n);
for (int i=0;i < n;i++) {
scanf("%d%d%d%d", &x[i], &y[i], &l[i], &w[i]);

}
int tx, ty;
scanf("%d%d", &tx, &ty);

int ans=-1;

for (int i=0;i < n;i++) {
if (tx <= x[i]+l[i] && tx >= x[i] && ty <= y[i]+w[i] && ty >= y[i]) {
ans=i+1;

}
}

printf("%d", ans);

return 0;
}

判断(p[i].x <= sx) && (p[i].x + p[i].a >= sx) && (p[i].y <= sy) && (p[i].y + p[i].b >= sy)是否为1

评测结果

编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 556 KiB, score = 10

测试数据 #1: Accepted, time = 0 ms, mem = 556 KiB, score = 10

测试数据 #2: Accepted, time = 0 ms, mem = 556 KiB, score = 10

测试数据 #3: Accepted, time = 0 ms, mem = 556 KiB, score = 10

测试数据 #4: Accepted, time = 0 ms, mem = 560 KiB, score = 10

测试数据 #5: Accepted, time = 15 ms, mem = 572 KiB, score = 10

测试数据 #6: Accepted, time = 15 ms, mem = 644 KiB, score = 10

测试数据 #7: Accepted, time = 31 ms, mem = 688 KiB, score = 10

测试数据 #8: Accepted, time = 46 ms, mem = 724 KiB, score = 10

测试数据 #9: Accepted, time = 31 ms, mem = 720 KiB, score = 10

Accepted, time = 138 ms, mem = 724 KiB, score = 100
代码
c++
#include <iostream>
#include <vector>
using namespace std;
struct place{int x,y,a,b;};
int main()
{
ios::sync_with_stdio(0);
int n,sx,sy,ans=-1;
cin>>n;
vector<place> p(n);
for(int i=0;i<n;i++)cin>>p[i].x>>p[i].y>>p[i].a>>p[i].b;
cin>>sx>>sy;
for(int i=0;i<n;i++)if(p[i].x<=sx&&p[i].x+p[i].a>=sx&&p[i].y<=sy&&p[i].y+p[i].b>=sy)ans=i+1;
cout<<ans;
return 0;
}


var
n,i,j,h,z:longint;
a:array[1..10100,1..4]of longint;
begin
readln(n);
for i:=1 to n do
readln(a[i,1],a[i,2],a[i,3],a[i,4]);
readln(h,z);
for i:=n downto 1 do
if (a[i,1]<=h) and (a[i,2]<=z) and (h<=(a[i,1]+a[i,3])) and (z<=(a[i,2]+a[i,4])) then
begin
writeln(i);
halt;
end;
writeln('-1');
end.

记录信息
评测状态    Accepted
题目  P1736 铺地毯
递交时间    2016-05-17 20:56:13
代码语言    C++
评测机 ShadowShore
消耗时间    185 ms
消耗内存    2144 KiB
评测时间    2016-05-17 20:56:15
评测结果
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 2140 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 2144 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 2144 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 2140 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 2144 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 2140 KiB, score = 10
测试数据 #6: Accepted, time = 31 ms, mem = 2140 KiB, score = 10
测试数据 #7: Accepted, time = 46 ms, mem = 2144 KiB, score = 10
测试数据 #8: Accepted, time = 46 ms, mem = 2140 KiB, score = 10
测试数据 #9: Accepted, time = 62 ms, mem = 2140 KiB, score = 10
Accepted, time = 185 ms, mem = 2144 KiB, score = 100
代码
#include <iostream>
using namespace std;
int n,ans = -1,x,y;
int a[100001],b[100001],c[100001],d[100001];
inline void point(int i) {
  if (!i) return;
  else {
    if(x>=a[i] && x<=a[i]+c[i] && y>=b[i] && y<=b[i]+d[i]) {
      ans = i;
      return;
    }
    point(i-1);
  }
}
int main() {
  cin >> n;
  for (int i = 1;i <= n;i++)
    cin >> a[i] >> b[i] >> c[i] >> d[i];
  cin >> x >> y;
  point(n);
  cout << ans;
  return 0;
}

#include <cstdio>

int p[10001][5];

int check(int a,int b[]){
int flag=1;
for(int i=1;i<=2;i++){
flag*=b[i]>=p[a][i];
flag*=b[i]<=p[a][i+2];
}
return flag;
}

int main(){
// freopen("in.txt","r",stdin);
int n,l,b[3];
scanf("%d",&n);
for(int i=1;i<=n;i++){
for(int j=1;j<=2;j++)
scanf("%d",&p[i][j]);
for(int j=1;j<=2;j++){
scanf("%d",&l);
p[i][j+2]=p[i][j]+l;
}
}
scanf("%d%d",&b[1],&b[2]);
int flag=-1;
for(int i=1;i<=n;i++)
if(check(i,b))
flag=i;
printf("%d",flag);
return 0;
}

###C++ Code
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int reada[10005],readb[10005],readx[10005],ready[10005],n,x,y,re=-1;
int main() {
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%d%d%d%d",reada+i,readb+i,readx+i,ready+i);
scanf("%d%d",&x,&y);
for (int i=n;i>0;i--) {
if (reada[i]<=x && reada[i]+readx[i]>=x && readb[i]<=y && readb[i]+ready[i]>=y) {
re=i;
break;
}
}
printf("%d",re);
return 0;
}

离线做法

试想题目一开始就告诉了我们最后要查询的点是哪个
那对于之后的n次覆盖
我们只要判断是否覆盖了目标点就行了 覆盖了就更新答案

现在题目是先给出的覆盖操作 最后给的查询目标点
我们完全可以先把覆盖操作读入后存储下来
当知道目标点之后再去计算答案
而且现在不用从前往后找了
答案是最后一次覆盖 所以一定在最后面
直接倒着找就行了

var
a,b,c,d:array[0..10009] of longint;
n,x,y,i:longint;
begin
readln(n);
for i:=1 to n do
begin
readln(a[i],b[i],x,y);
c[i]:=a[i]+x;
d[i]:=b[i]+y;
end;
read(x,y);
for i:=n downto 1 do
if (x>=a[i]) and (x<=c[i]) and (y>=b[i]) and (y<=d[i]) then
begin writeln(i); halt; end;
writeln(-1);
end.

#include <stdio.h>
struct point
{int x,y,a,b;}it[10010];
int main()
{
int i,n,ansx,ansy;
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d%d%d%d",&it[i].x,&it[i].y,&it[i].a,&it[i].b);
scanf("%d%d",&ansx,&ansy);
for(i=n;i>=1;i--)
{
if(it[i].x<=ansx&&it[i].x+it[i].a>=ansx&&it[i].y<=ansy&&it[i].y+it[i].b>=ansy)
{
printf("%d",i);
return 0;
}
}
printf("-1");
}

#include <iostream>
#include <vector>
#include <cstdio>

using namespace std;

vector<int>x1;
vector<int>x2;
vector<int>y1;
vector<int>y2;

int main()
{
int f;
int x,y;
cin>>f;
int i,j;
for(i=0;i<f;++i)
{
scanf("%d",&j);
x1.push_back(j);
scanf("%d",&j);
x2.push_back(j);
scanf("%d",&j);
y1.push_back(j);
scanf("%d",&j);
y2.push_back(j);
}
cin>>x>>y;
j=-1;
for(i=0;i<f;++i)
{
if(x>=x1[i]&&x<=x1[i]+y1[i]&&y>=x2[i]&&y<=x2[i]+y2[i])j=i+1;
}
cout<<j;
return 0;
}

#include <cstdio>
#include <cstdlib>

using namespace std;

int n;
int a[10005], b[10005], g[10005], k[10005];

int main(int argc, const char *argv[])
{
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
scanf("%d %d %d %d", &a[i], &b[i], &g[i], &k[i]);
int x, y;
scanf("%d %d", &x, &y);
int ans = -1;
for (int i = n; i >= 1; --i)
{
if (a[i] <= x && x <= a[i] + g[i] && b[i] <= y && y <= b[i] + k[i])
{
ans = i;
break;
}
}
printf("%d\n", ans);
return 0;
}

貌似不用搜索，直接维护一个点
#include <cstdio>
#include <cstring>
#include <algorithm>
const int maxn=10005;
int main()
{
int a[maxn],b[maxn],g[maxn],k[maxn];
int N;scanf("%d",&N);
for(int i=0;i<N;i++) {
scanf("%d%d%d%d",&a[i],&b[i],&g[i],&k[i]);
}
int px,py;
int cover=-1;
scanf("%d%d",&px,&py);
for(int i=0;i<N;i++) {
if(a[i]<=px && a[i]+g[i]>=px) {
if(b[i]<=py && b[i]+k[i]>=py )
cover=i+1;
}
}
printf("%d",cover);
return 0;
}

记录信息
评测状态 Accepted
题目 P1736 铺地毯
递交时间 2015-08-20 20:50:44
代码语言 C++
评测机 Jtwd2
消耗时间 41 ms
消耗内存 632 KiB
评测时间 2015-08-20 20:50:45
评测结果
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 628 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 624 KiB, score = 10
测试数据 #2: Accepted, time = 11 ms, mem = 628 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 624 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 632 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 632 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 624 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 628 KiB, score = 10
测试数据 #8: Accepted, time = 15 ms, mem = 624 KiB, score = 10
测试数据 #9: Accepted, time = 15 ms, mem = 628 KiB, score = 10
Accepted, time = 41 ms, mem = 632 KiB, score = 100
代码
#include <iostream>
#include <stdio.h>
using namespace std;
struct point
{
int x,y,a,b;
};
point it[10010];
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d%d%d%d",&it[i].x,&it[i].y,&it[i].a,&it[i].b);
int ansx,ansy;
scanf("%d%d",&ansx,&ansy);
for(int i=n;i>=1;i--)
{
if(it[i].x<=ansx&&it[i].x+it[i].a>=ansx&&it[i].y<=ansy&&it[i].y+it[i].b>=ansy)
{
printf("%d",i);
return 0;
}
}
printf("-1");
}

var n,i,c,d:longint;
a,b,x,y:array[0..100000]of longint;
begin
read(n);
for i:=1 to n do
begin
read(a[i],b[i],x[i],y[i]);
x[i]:=a[i]+x[i];
y[i]:=b[i]+y[i];
end;
read(c,d);
for i:=n downto 1 do
if (a[i]<=c)and(b[i]<=d)and(x[i]>=c)and(y[i]>=d) then
begin writeln(i); exit; end;
writeln(-1);
end.

确定是搜索。。

#include<iostream>
#include<cstring>
using namespace std;
const int MAXN=1000000;

int a[MAXN],b[MAXN],g[MAXN],k[MAXN];

int main()
{
int n;
cin>>n;
for(int i=1; i<=n; i++)
cin>>a[i]>>b[i]>>g[i]>>k[i];

int x,y;
cin>>x>>y;
int ans=-1;
for(int i=1; i<=n; i++)
if(x>=a[i] && x<=a[i]+g[i] && y>=b[i] &&y<=b[i]+k[i])
ans=i;
cout<<ans;
return 0;
}

program zhen;
var
a,b,g,k:array[0..10000]of longint;
i,j,n,x,y,ans:longint;
begin
readln(n);
for i:=1 to n do read(a[i],b[i],g[i],k[i]);
readln(x,y);
ans:=-1;
for i:=1 to n do
if (x>=a[i]) and (x<=a[i]+g[i]) and (y>=b[i]) and (y<=b[i]+k[i]) then
ans:=i;
writeln(ans);
end.