思路:用链表来保存每一个地毯的左上、右下的坐标,然后从头节点开始遍历链表,判断每个地毯是否包含此点
虽然用链表没有必要,我只是想尝试一下链表,练习一下
样例都能过,提交却只AC了两道题TAT(有AC的题目是不是可以证明这个解法的逻辑没用问题?)
求各位大佬帮我看看到底是那里出了问题,有一些是做题不必要的代码我是写来检查问题的(但是一直没有找到问题)我都用注释标注出来了
找了两个小时问题了,真破防了TAT
#include<bits/stdc++.h>
#define forr(i,a,b) for(int i=(a);i<(b);i++)
#define INIT() do{\
ios::sync_with_stdio(0); \
cin.tie(0);\
cout.tie(0);\
}while(0);
#define endl '\n'
//typedef unsigned long long ull;
//const int N = 1e8;
using namespace std;
struct node{
int left_dowm[2], right_up[2];
node* next;
};
void out_list(node *h){ // 顺序输出链表中所有元素( 写来检查错误的 )
cout<<endl;
cout<<"*******************************"<<endl;
cout<<endl;
h=h->next;
while(h){
cout<<h->left_dowm[0]<<" "<<h->left_dowm[1]<<endl;
cout<<h->right_up[0]<<" "<<h->right_up[1]<<endl;
h=h->next;
cout<<endl;
}
cout<<endl;
cout<<"*******************************"<<endl;
cout<<endl;
}
int fine_list(node *h, int x, int y){
int ans=0, unans=0; // 初始化返回值,返回包含该点的地毯个数
h=h->next;
node *head2, *pass2; // 用来保存一条不符合条件的链表( 只是用来检查错误 )
head2=pass2=new node;
while(h){
if(x>=h->left_dowm[0]&&x<=h->right_up[0]&&y>=h->left_dowm[1]&&y<=h->right_up[1]){
ans++; // 符合条件的数量
}else{
pass2->next=h;pass2=h;
unans++; // 不符合条件的数量
}
h=h->next;
}
out_list(head2);
cout<<unans<<" ";
return ans;
}
void function1(){
int n, a, b, c, d, x, y, answer;
cin>>n;
node *head, *pass, *now;
head = now = new node; // head是头节点,now和 pass用于初始化链表
forr(i,0,n){ // 初始化链表,每个节点对应一个地毯,保存该地毯左下和右上的坐标
cin>>a>>b>>c>>d;
pass=new node;
pass->left_dowm[0]=a;pass->left_dowm[1]=b;pass->right_up[0]=a+c-1;pass->right_up[1]=b+d-1; // 0->x坐标 1->y坐标
now->next=pass;now=pass; // 常规的初始化链表的操作,
}
now->next=NULL; // head->node1->node2->......noden->NULL
// out_list(head);
cin>>x>>y;
answer=fine_list(head,x,y); // 比较该点落在多少个地毯上
if(answer==0) cout<<-1;
else cout<<answer;
delete head, pass, now;
}
int main(){
INIT();
function1();
return 0;
}