比赛 |
20120722 |
评测结果 |
AWWWWWWWTT |
题目名称 |
切割矩形 |
最终得分 |
10 |
用户昵称 |
Citron酱 |
运行时间 |
2.003 s |
代码语言 |
C++ |
内存使用 |
1.32 MiB |
提交时间 |
2012-07-22 13:03:04 |
显示代码纯文本
#include <cstdio>
#include <cstdlib>
#define I_F "cutting.in"
#define O_F "cutting.out"
const int MAXn=30000;
const int MAXq=30000;
const short P=20;
struct lib
{
long x1,x2,y1,y2;
lib *prep,*succ;
};
struct line
{
long x1,x2,y;
};
lib pool[MAXn];
lib *ph, *s;
line p[MAXq];
long ans;
int n,q;
template<typename Any>
inline void Swap(Any&, Any&);
void Input();
void Sort(const int&, const int&);
void Search();
void Output();
int main()
{
freopen(I_F,"r",stdin);
freopen(O_F,"w",stdout);
short t;
for (scanf("%hd",&t); t>0; --t)
{
Input();
Sort(0,q-1);
Search();
Output();
}
return 0;
}
template<typename Any>
inline void Swap(Any &a, Any &b)
{
Any t=a;
a=b;
b=t;
}
void Input()
{
ph=pool;
s=NULL;
lib *temp;
scanf("%d",&n);
for (int i=0; i<n; ++i)
{
temp=s;
s=ph++;
s->succ=temp;
s->prep=NULL;
if (temp!=NULL)
temp->prep=s;
scanf("%ld%ld%ld%ld",&s->x1,&s->y1,&s->x2,&s->y2);
}
scanf("%d",&q);
for (int i=0; i<q; ++i)
scanf("%ld%ld%ld%*d",&p[i].x1,&p[i].y,&p[i].x2);
}
void Sort(const int &l, const int &r)
{
if (r-l>P)
{
long x=p[l+rand()%(r-l+1)].y;
int i=l, j=r;
do
{
while (p[i].y<x) ++i;
while (p[j].y>x) --j;
if (i<=j)
Swap(p[i++],p[j--]);
} while (i<j);
if (i<r) Sort(i,r);
if (l<j) Sort(l,j);
}
else
{
bool flag=true;
for (int i=l; i<r && flag; ++i)
{
flag=false;
for (int j=r; j>i; --j)
if (p[j-1].y>p[j].y)
Swap(p[j-1],p[j]),
flag=true;
}
}
}
void Search()
{
ans=0;
for (int i=0; i<q; ++i)
for (lib *j=s; j!=NULL; j=j->succ)
if (j->y2<p[i].y)
{
if (j->succ!=NULL)
j->succ->prep=j->prep;
if (j->prep!=NULL)
j->prep->succ=j->succ;
else
s=j->succ;
}
else
if (((j->y1==p[i].y || j->y2==p[i].y) && j->x1<=p[i].x2 && j->x2>=p[i].x1) ||
((j->y1<p[i].y && j->y2>p[i].y) && ((p[i].x1<=j->x1 && p[i].x2>=j->x1) ||
(p[i].x1<=j->x2 && p[i].x2>=j->x2))))
++ans;
}
void Output()
{
printf("%ld\n",ans);
}